Submission #544957

#	Time	Username	Problem	Language	Result	Execution time	Memory
544957		byunjaewoo	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	1489 ms	92792 KiB

matryoshka

#include <bits/stdc++.h>
using namespace std;

const int S=(1<<19), Nmax=200010;
class SegTree {
public:
    void Update(int k, int v) {Update(1, 1, S, k, v);}
    int Query(int l, int r) {return Query(1, 1, S, l, r);}
private:
    int Tree[2*S];
    void Update(int node, int s, int e, int k, int v) {
        if(s==e) {
            Tree[node]=max(Tree[node], v);
            return;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) Update(lch, s, m, k, v);
        else Update(rch, m+1, e, k, v);
        Tree[node]=max(Tree[lch], Tree[rch]);
    }
    int Query(int node, int s, int e, int l, int r) {
        if(s>r || l>e) return 0;
        if(l<=s && e<=r) return Tree[node];
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        return max(Query(lch, s, m, l, r), Query(rch, m+1, e, l, r));
    }
}T;
int N, Q, cntx, cnty, ans[Nmax];
struct Data {int x, y, op;};
set<int> Sx, Sy;
map<int, int> Mx, My;
vector<Data> V;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>Q;
    for(int i=1; i<=N; i++) {
        int x, y; cin>>x>>y;
        Sx.insert(x); Sy.insert(y);
        V.push_back({x, y, 0});
    }
    for(int i=1; i<=Q; i++) {
        int x, y; cin>>x>>y;
        Sx.insert(x); Sy.insert(y);
        V.push_back({x, y, i});
    }
    for(int i:Sx) Mx[i]=++cntx;
    for(int i:Sy) My[i]=++cnty;
    sort(V.begin(), V.end(), [](Data u, Data v) {return (u.x!=v.x)?(u.x>v.x):((u.y!=v.y)?(u.y<v.y):(u.op<v.op));});
    for(Data i:V) {
        i.x=Mx[i.x], i.y=My[i.y];
        int tmp=T.Query(1, i.y);
        if(i.op) ans[i.op]=tmp;
        else T.Update(i.y, tmp+1);
    }
    for(int i=1; i<=Q; i++) cout<<ans[i]<<"\n";
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49