oj.uz

답안 #207679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
207679 2020-03-08T14:45:07 Z nvmdava Examination (JOI19_examination) C++17
2 / 100
 2050 ms 484384 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(r)
            w += r -> query(m + 1, R, y);
        if(l)
            w += l -> query(L, m, 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)
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 380 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 424 KB Output is correct
7 Correct 31 ms 11256 KB Output is correct
8 Correct 32 ms 11384 KB Output is correct
9 Correct 31 ms 11384 KB Output is correct
10 Correct 17 ms 4728 KB Output is correct
11 Correct 18 ms 4728 KB Output is correct
12 Correct 9 ms 504 KB Output is correct
13 Correct 32 ms 11384 KB Output is correct
14 Correct 32 ms 11384 KB Output is correct
15 Correct 32 ms 11384 KB Output is correct
16 Correct 14 ms 3960 KB Output is correct
17 Correct 15 ms 4216 KB Output is correct
18 Correct 8 ms 504 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2050 ms 481948 KB Output is correct
2 Correct 2003 ms 483988 KB Output is correct
3 Correct 2020 ms 484384 KB Output is correct
4 Correct 528 ms 103840 KB Output is correct
5 Correct 485 ms 100128 KB Output is correct
6 Correct 157 ms 6112 KB Output is correct
7 Correct 1852 ms 484168 KB Output is correct
8 Correct 1824 ms 484264 KB Output is correct
9 Correct 1634 ms 484288 KB Output is correct
10 Incorrect 345 ms 79144 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2050 ms 481948 KB Output is correct
2 Correct 2003 ms 483988 KB Output is correct
3 Correct 2020 ms 484384 KB Output is correct
4 Correct 528 ms 103840 KB Output is correct
5 Correct 485 ms 100128 KB Output is correct
6 Correct 157 ms 6112 KB Output is correct
7 Correct 1852 ms 484168 KB Output is correct
8 Correct 1824 ms 484264 KB Output is correct
9 Correct 1634 ms 484288 KB Output is correct
10 Incorrect 345 ms 79144 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 380 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 424 KB Output is correct
7 Correct 31 ms 11256 KB Output is correct
8 Correct 32 ms 11384 KB Output is correct
9 Correct 31 ms 11384 KB Output is correct
10 Correct 17 ms 4728 KB Output is correct
11 Correct 18 ms 4728 KB Output is correct
12 Correct 9 ms 504 KB Output is correct
13 Correct 32 ms 11384 KB Output is correct
14 Correct 32 ms 11384 KB Output is correct
15 Correct 32 ms 11384 KB Output is correct
16 Correct 14 ms 3960 KB Output is correct
17 Correct 15 ms 4216 KB Output is correct
18 Correct 8 ms 504 KB Output is correct
19 Correct 2050 ms 481948 KB Output is correct
20 Correct 2003 ms 483988 KB Output is correct
21 Correct 2020 ms 484384 KB Output is correct
22 Correct 528 ms 103840 KB Output is correct
23 Correct 485 ms 100128 KB Output is correct
24 Correct 157 ms 6112 KB Output is correct
25 Correct 1852 ms 484168 KB Output is correct
26 Correct 1824 ms 484264 KB Output is correct
27 Correct 1634 ms 484288 KB Output is correct
28 Incorrect 345 ms 79144 KB Output isn't correct
29 Halted 0 ms 0 KB -