Submission #320929

#	Time	Username	Problem	Language	Result	Execution time	Memory
320929		lohacho	Matryoshka (JOI16_matryoshka)	C++14	100 / 100	634 ms	26192 KiB

matryoshka

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)8e5 + 4;
int N, Q;
struct Data{
    int a, b, num;
    bool operator<(const Data&r)const{
        return a < r.a || (a == r.a && b > r.b);
    }
};
Data doll[NS], ask[NS];
int ans[NS];
vector<int> srt;
int tree[NS * 4];

void push(int num, int s, int e, int pos, int val){
    if(pos < s || pos > e) return;
    if(s == e){
        tree[num] = max(tree[num], val);
        return;
    }
    push(num * 2, s, (s + e) / 2, pos, val), push(num * 2 + 1, (s + e) / 2 + 1, e, pos, val);
    tree[num] = max(tree[num * 2], tree[num * 2 + 1]);
}

int get(int num, int s, int e, int fs, int fe){
    if(fe < s || fs > e){
        return 0;
    }
    if(s >= fs && e <= fe){
        return tree[num];
    }
    return max(get(num * 2, s, (s + e) / 2, fs, fe), get(num * 2 + 1, (s + e) / 2 + 1, e, fs, fe));
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> Q;
    for(int i = 1; i <= N; ++i){
        cin >> doll[i].a >> doll[i].b;
        srt.push_back(doll[i].a), srt.push_back(doll[i].b);
    }
    for(int i = 1; i <= Q; ++i){
        cin >> ask[i].a >> ask[i].b;
        srt.push_back(ask[i].a), srt.push_back(ask[i].b);
        ask[i].num = i;
    }
    sort(srt.begin(), srt.end());
    srt.erase(unique(srt.begin(), srt.end()), srt.end());
    for(int i = 1; i <= N; ++i){
        doll[i].a = lower_bound(srt.begin(), srt.end(), doll[i].a) - srt.begin() + 1;
        doll[i].b = lower_bound(srt.begin(), srt.end(), doll[i].b) - srt.begin() + 1;
    }
    for(int i = 1; i <= Q; ++i){
        ask[i].a = lower_bound(srt.begin(), srt.end(), ask[i].a) - srt.begin() + 1;
        ask[i].b = lower_bound(srt.begin(), srt.end(), ask[i].b) - srt.begin() + 1;
    }
    sort(doll + 1, doll + N + 1);
    sort(ask + 1, ask + Q + 1);
    int j = Q;
    for(int i = N; i >= 1; --i){
        while(j && ask[j].a > doll[i].a){
            ans[ask[j].num] = get(1, 1, (int)srt.size(), 1, ask[j].b);
            --j;
        }
        int val = get(1, 1, (int)srt.size(), 1, doll[i].b);
        push(1, 1, (int)srt.size(), doll[i].b, val + 1);
    }
    while(j){
        ans[ask[j].num] = get(1, 1, (int)srt.size(), 1, ask[j].b);
        --j;
    }
    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