oj.uz

Submission #896452

# Submission time Handle Problem Language Result Execution time Memory
896452 2024-01-01T13:21:43 Z Andrey Examination (JOI19_examination) C++14
100 / 100
 974 ms 314388 KB 
#include<bits/stdc++.h>
using namespace std;

vector<pair<long long,long long>> seg(3000001,{-1,-1});
vector<long long> wow[3000001];
vector<long long> wut[3000001];
long long p = 0;

long long banana(const vector<long long>& haha, long long a) {
    if(haha.empty() || haha[haha.size()-1] < a) {
        return 0;
    }
    long long l = 0,r = haha.size()-1;
    while(l < r) {
        long long m = (l+r)/2;
        if(haha[m] >= a) {
            r = m;
        }
        else {
            l = m+1;
        }
    }
    return haha.size()-l;
}

void ins(long long l, long long r, long long x, long long pos, long long y, long long sb) {
    wow[x].push_back(y);
    wut[x].push_back(sb);
    if(l == r) {
        return;
    }
    long long m = (l+r)/2;
    if(pos <= m) {
        if(seg[x].first == -1) {
            p++;
            seg[x] = {p,seg[x].second};
        }
        ins(l,m,seg[x].first,pos,y,sb);
    }
    else {
        if(seg[x].second == -1) {
            p++;
            seg[x] = {seg[x].first,p};
        }
        ins(m+1,r,seg[x].second,pos,y,sb);
    }
}

long long calc(long long l, long long r, long long x, long long ql, long long qr, bool yeah, long long a) {
    if(x == -1) {
        return 0;
    }
    if(ql == l && qr == r) {
        if(yeah) {
            return banana(wow[x],a);
        }
        else {
            return banana(wut[x],a);
        }
    }
    long long m = (l+r)/2;
    if(qr <= m) {
        return calc(l,m,seg[x].first,ql,qr,yeah,a);
    }
    else if(ql > m) {
        return calc(m+1,r,seg[x].second,ql,qr,yeah,a);
    }
    else {
        return calc(l,m,seg[x].first,ql,m,yeah,a)+calc(m+1,r,seg[x].second,m+1,qr,yeah,a);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,q,a,b,c;
    cin >> n >> q;
    for(long long i = 0; i < n; i++) {
        cin >> a >> b;
        ins(0,INT_MAX,0,a,b,a+b);
    }
    for(int i = 0; i <= 3000000; i++) {
        sort(wut[i].begin(),wut[i].end());
        sort(wow[i].begin(),wow[i].end());
    }
    for(int i = 0; i < q; i++) {
        cin >> a >> b >> c;
        if(a+b >= c) {
            cout << calc(0,INT_MAX,0,a,INT_MAX,true,b) << "\n";
        }
        else {
            cout << calc(0,INT_MAX,0,a,c-b,false,c)+calc(0,INT_MAX,0,c-b+1,INT_MAX,true,b) << "\n";
        }
    }
    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 188496 KB Output is correct
2 Correct 47 ms 188244 KB Output is correct
3 Correct 50 ms 188296 KB Output is correct
4 Correct 45 ms 188288 KB Output is correct
5 Correct 45 ms 188196 KB Output is correct
6 Correct 47 ms 188252 KB Output is correct
7 Correct 66 ms 192592 KB Output is correct
8 Correct 66 ms 192652 KB Output is correct
9 Correct 60 ms 192432 KB Output is correct
10 Correct 59 ms 192604 KB Output is correct
11 Correct 56 ms 190360 KB Output is correct
12 Correct 53 ms 190044 KB Output is correct
13 Correct 60 ms 192596 KB Output is correct
14 Correct 59 ms 192600 KB Output is correct
15 Correct 59 ms 192580 KB Output is correct
16 Correct 56 ms 190296 KB Output is correct
17 Correct 61 ms 192596 KB Output is correct
18 Correct 49 ms 190344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 252416 KB Output is correct
2 Correct 709 ms 252456 KB Output is correct
3 Correct 686 ms 252820 KB Output is correct
4 Correct 564 ms 252768 KB Output is correct
5 Correct 579 ms 242412 KB Output is correct
6 Correct 307 ms 242488 KB Output is correct
7 Correct 671 ms 252792 KB Output is correct
8 Correct 651 ms 252836 KB Output is correct
9 Correct 621 ms 253612 KB Output is correct
10 Correct 550 ms 241156 KB Output is correct
11 Correct 491 ms 252648 KB Output is correct
12 Correct 205 ms 240900 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 252416 KB Output is correct
2 Correct 709 ms 252456 KB Output is correct
3 Correct 686 ms 252820 KB Output is correct
4 Correct 564 ms 252768 KB Output is correct
5 Correct 579 ms 242412 KB Output is correct
6 Correct 307 ms 242488 KB Output is correct
7 Correct 671 ms 252792 KB Output is correct
8 Correct 651 ms 252836 KB Output is correct
9 Correct 621 ms 253612 KB Output is correct
10 Correct 550 ms 241156 KB Output is correct
11 Correct 491 ms 252648 KB Output is correct
12 Correct 205 ms 240900 KB Output is correct
13 Correct 749 ms 252724 KB Output is correct
14 Correct 721 ms 252344 KB Output is correct
15 Correct 685 ms 252584 KB Output is correct
16 Correct 632 ms 252908 KB Output is correct
17 Correct 574 ms 242540 KB Output is correct
18 Correct 309 ms 242496 KB Output is correct
19 Correct 764 ms 253232 KB Output is correct
20 Correct 770 ms 252616 KB Output is correct
21 Correct 776 ms 252976 KB Output is correct
22 Correct 527 ms 241032 KB Output is correct
23 Correct 487 ms 252364 KB Output is correct
24 Correct 201 ms 240768 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 188496 KB Output is correct
2 Correct 47 ms 188244 KB Output is correct
3 Correct 50 ms 188296 KB Output is correct
4 Correct 45 ms 188288 KB Output is correct
5 Correct 45 ms 188196 KB Output is correct
6 Correct 47 ms 188252 KB Output is correct
7 Correct 66 ms 192592 KB Output is correct
8 Correct 66 ms 192652 KB Output is correct
9 Correct 60 ms 192432 KB Output is correct
10 Correct 59 ms 192604 KB Output is correct
11 Correct 56 ms 190360 KB Output is correct
12 Correct 53 ms 190044 KB Output is correct
13 Correct 60 ms 192596 KB Output is correct
14 Correct 59 ms 192600 KB Output is correct
15 Correct 59 ms 192580 KB Output is correct
16 Correct 56 ms 190296 KB Output is correct
17 Correct 61 ms 192596 KB Output is correct
18 Correct 49 ms 190344 KB Output is correct
19 Correct 677 ms 252416 KB Output is correct
20 Correct 709 ms 252456 KB Output is correct
21 Correct 686 ms 252820 KB Output is correct
22 Correct 564 ms 252768 KB Output is correct
23 Correct 579 ms 242412 KB Output is correct
24 Correct 307 ms 242488 KB Output is correct
25 Correct 671 ms 252792 KB Output is correct
26 Correct 651 ms 252836 KB Output is correct
27 Correct 621 ms 253612 KB Output is correct
28 Correct 550 ms 241156 KB Output is correct
29 Correct 491 ms 252648 KB Output is correct
30 Correct 205 ms 240900 KB Output is correct
31 Correct 749 ms 252724 KB Output is correct
32 Correct 721 ms 252344 KB Output is correct
33 Correct 685 ms 252584 KB Output is correct
34 Correct 632 ms 252908 KB Output is correct
35 Correct 574 ms 242540 KB Output is correct
36 Correct 309 ms 242496 KB Output is correct
37 Correct 764 ms 253232 KB Output is correct
38 Correct 770 ms 252616 KB Output is correct
39 Correct 776 ms 252976 KB Output is correct
40 Correct 527 ms 241032 KB Output is correct
41 Correct 487 ms 252364 KB Output is correct
42 Correct 201 ms 240768 KB Output is correct
43 Correct 932 ms 313592 KB Output is correct
44 Correct 872 ms 314232 KB Output is correct
45 Correct 868 ms 314264 KB Output is correct
46 Correct 817 ms 312980 KB Output is correct
47 Correct 565 ms 245820 KB Output is correct
48 Correct 321 ms 243216 KB Output is correct
49 Correct 938 ms 314376 KB Output is correct
50 Correct 886 ms 314264 KB Output is correct
51 Correct 974 ms 314388 KB Output is correct
52 Correct 545 ms 244224 KB Output is correct
53 Correct 715 ms 311736 KB Output is correct