oj.uz

Submission #207680

# Submission time Handle Problem Language Result Execution time Memory
207680 2020-03-08T14:48:49 Z nvmdava Examination (JOI19_examination) C++17
2 / 100
 2023 ms 482076 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 100000
#define MOD 1000000007
#define INF 0x3f3f3f3f

vector<pair<int, pair<int, int> > > ar;
vector<pair<pair<int, int>, pair<int, int> > > qu;
map<int, int> scmp, tcmp;

struct Y {
    int val = 0;
    Y *l = NULL, *r = NULL;

    int query(int L, int R, int y){
        if(R <= y)
            return val;
        if(L > y)
            return 0;
        int m = (L + R) >> 1;
        int w = 0;
        if(l)
            w += l -> query(L, m, y);
        if(r && m < y)
            w += r -> query(m + 1, R, y);
        return w;
    }
    void update(int L, int R, int y){
        ++val;
        if(L == R)
            return;
        int m = (L + R) >> 1;
        if(m >= y){
            if(!l)
                l = new Y();
            l -> update(L, m, y);
        } else {
            if(!r)
                r = new Y();
            r -> update(m + 1, R, y);
        }
    }
};

struct X {
    Y *val = new Y();
    X *l = NULL, *r = NULL;

    int query(int L, int R, int x, int y){
        if(R <= x)
            return val -> query(1, N, y);
        if(L > x)
            return 0;
        int m = (L + R) >> 1;
        int w = 0;
        if(l)
            w += l -> query(L, m, x, y);
        if(r && m < x)
            w += r -> query(m + 1, R, x, y);
        return w;
    }
    void update(int L, int R, int x, int y){
        val -> update(1, N, y);
        if(L == R) return;
        int m = (L + R) >> 1;
        if(m >= x){
            if(!l)
                l = new X();
            l -> update(L, m, x, y);
        } else {
            if(!r)
                r = new X();
            r -> update(m + 1, R, x, y);
        }
    }
} *seg = new X();

int ans[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin>>n>>q;
    int mxs = 0, mxt = 0;
    for(int i = 1; i <= n; ++i){
        int s, t;
        cin>>s>>t;
        mxs = max(mxs, s);
        mxt = max(mxt, t);
        ar.push_back({s + t, {s, t}});
        scmp[s] = 0;
        tcmp[t] = 0;
    }
    int w;

    w = 0;
    for(auto& x : scmp)
        x.ss = ++w;
    w = 0;
    for(auto& x : tcmp)
        x.ss = ++w;
    int ss = scmp.size(), ts = tcmp.size();
    for(auto& x : ar){
        x.ss.ff = ss + 1 - scmp[x.ss.ff];
        x.ss.ss = ts + 1 - tcmp[x.ss.ss];
    }

    sort(ar.rbegin(), ar.rend());

    for(int i = 1; i <= q; ++i){
        int a, b, c;
        cin>>a>>b>>c;
        if(a > mxs || b > mxt)
            continue;
        a = scmp.lower_bound(a) -> ss;
        b = tcmp.lower_bound(b) -> ss;
        a = ss + 1 - a;
        b = ts + 1 - b;
        qu.push_back({{c, i}, {a, b}});
    }
    sort(qu.rbegin(), qu.rend());

    w = 0;

    for(auto& x : qu){
        while(w != n && ar[w].ff >= x.ff.ff){
            seg -> update(1, N, ar[w].ss.ff, ar[w].ss.ss);
            ++w;
        }
        ans[x.ff.ss] = seg -> query(1, N, x.ss.ff, x.ss.ss);
    }
    for(int i = 1; i <= q; ++i)
        cout<<ans[i]<<'\n';
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 31 ms 11256 KB Output is correct
8 Correct 31 ms 11384 KB Output is correct
9 Correct 31 ms 11384 KB Output is correct
10 Correct 18 ms 4728 KB Output is correct
11 Correct 17 ms 4600 KB Output is correct
12 Correct 10 ms 508 KB Output is correct
13 Correct 33 ms 11512 KB Output is correct
14 Correct 32 ms 11384 KB Output is correct
15 Correct 34 ms 11384 KB Output is correct
16 Correct 14 ms 3964 KB Output is correct
17 Correct 15 ms 4088 KB Output is correct
18 Correct 8 ms 504 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1964 ms 481672 KB Output is correct
2 Correct 2023 ms 481744 KB Output is correct
3 Correct 1951 ms 482076 KB Output is correct
4 Correct 592 ms 102280 KB Output is correct
5 Correct 464 ms 98516 KB Output is correct
6 Correct 158 ms 5216 KB Output is correct
7 Correct 1828 ms 481824 KB Output is correct
8 Correct 1828 ms 481844 KB Output is correct
9 Correct 1605 ms 481808 KB Output is correct
10 Incorrect 327 ms 77356 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1964 ms 481672 KB Output is correct
2 Correct 2023 ms 481744 KB Output is correct
3 Correct 1951 ms 482076 KB Output is correct
4 Correct 592 ms 102280 KB Output is correct
5 Correct 464 ms 98516 KB Output is correct
6 Correct 158 ms 5216 KB Output is correct
7 Correct 1828 ms 481824 KB Output is correct
8 Correct 1828 ms 481844 KB Output is correct
9 Correct 1605 ms 481808 KB Output is correct
10 Incorrect 327 ms 77356 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 31 ms 11256 KB Output is correct
8 Correct 31 ms 11384 KB Output is correct
9 Correct 31 ms 11384 KB Output is correct
10 Correct 18 ms 4728 KB Output is correct
11 Correct 17 ms 4600 KB Output is correct
12 Correct 10 ms 508 KB Output is correct
13 Correct 33 ms 11512 KB Output is correct
14 Correct 32 ms 11384 KB Output is correct
15 Correct 34 ms 11384 KB Output is correct
16 Correct 14 ms 3964 KB Output is correct
17 Correct 15 ms 4088 KB Output is correct
18 Correct 8 ms 504 KB Output is correct
19 Correct 1964 ms 481672 KB Output is correct
20 Correct 2023 ms 481744 KB Output is correct
21 Correct 1951 ms 482076 KB Output is correct
22 Correct 592 ms 102280 KB Output is correct
23 Correct 464 ms 98516 KB Output is correct
24 Correct 158 ms 5216 KB Output is correct
25 Correct 1828 ms 481824 KB Output is correct
26 Correct 1828 ms 481844 KB Output is correct
27 Correct 1605 ms 481808 KB Output is correct
28 Incorrect 327 ms 77356 KB Output isn't correct
29 Halted 0 ms 0 KB -