oj.uz

Submission #320927

# Submission time Handle Problem Language Result Execution time Memory
320927 2020-11-10T09:17:23 Z lohacho None (JOI16_matryoshka) C++14
0 / 100
 1 ms 492 KB 
#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;
    }
};
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 - 1);
        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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Incorrect 1 ms 364 KB Output isn't correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Incorrect 1 ms 364 KB Output isn't correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Incorrect 1 ms 364 KB Output isn't correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Incorrect 1 ms 364 KB Output isn't correct