oj.uz

Submission #1033796

# Submission time Handle Problem Language Result Execution time Memory
1033796 2024-07-25T06:31:05 Z vjudge1 Examination (JOI19_examination) C++17
100 / 100
 575 ms 41456 KB 
#include <bits/stdc++.h>

#define int long long
#define ll long long
#define pb push_back

using namespace std;

struct point{
    int a, b, c, id, val;
};
vector<point> student;
const int maxn = 1e6 + 10;
int ans[maxn];

bool cmp(point x, point y){
    if(x.a != y.a) return x.a > y.a;
    if(x.b != y.b) return x.b < y.b;
    return x.c < y.c;
}

void inv(point &a){
    a.a = -a.a;
    a.b = -a.b;
    a.c = -a.c;
}

int bit[maxn];

int getsum(int i){
    ll sum = 0;
    while(i > 0){
        sum+=bit[i];
        i-=(i & (-i));
    }
    return sum;
}

void update(int i, int v){
    while(i < maxn){
        bit[i]+=v;
        i+=(i & (-i));
    }
}

void dnc(int l, int r){
    if(l + 1 == r) return;
    int mid = (l + r)/2;
    dnc(l , mid); dnc(mid, r);
    vector<pair<int,int>> rec; vector<point> tmp;
    int a = l, b = mid, sum = 0;

    while(a < mid && b < r) {
        if(student[a].b > student[b].b){
            update(student[a].c, student[a].val);
            sum+=student[a].val;
            rec.push_back({student[a].c,student[a].val});
            tmp.push_back(student[a++]);
        }
        else{
            ans[student[b].id] += sum - getsum(student[b].c);
            tmp.push_back(student[b++]);
        }
    }
    while(a < mid) tmp.push_back(student[a++]);
    while(b < r) ans[student[b].id] += sum - getsum(student[b].c), tmp.push_back(student[b++]);
    for(int i = l ; i < r ; ++i) student[i] = tmp[i - l];

    for(auto x: rec) update(x.first, -x.second);
    vector<pair<int,int>> ().swap(rec);
    vector<point> ().swap(tmp);
}


signed main(){
    int n, q;
    cin >> n >> q;
    vector<int> compress;
    compress.pb(-1e18); compress.pb(1e18);
    for(int i = 0; i < n; i++){
        point tmp; cin >> tmp.a >> tmp.b;
        tmp.c = tmp.a + tmp.b; tmp.id = 0; tmp.val = 1;
        // inv(tmp);
        compress.pb(tmp.a);compress.pb(tmp.b);compress.pb(tmp.c);
        student.pb(tmp);
    }

    int cnt = 1;
    int _q = q;
    while(q--){
        point tmp;
        cin >> tmp.a >> tmp.b >> tmp.c;
        tmp.a--; tmp.b--; tmp.c--;
        tmp.val = 0 ;
        compress.pb(tmp.a); compress.pb(tmp.b); compress.pb(tmp.c);
        tmp.id = cnt;
        // inv(tmp);
        cnt++;
        student.pb(tmp);
    }
    sort(compress.begin(),compress.end());
    for(auto &x : student){
        x.a = lower_bound(compress.begin(),compress.end(),x.a) - compress.begin();
        x.b = lower_bound(compress.begin(),compress.end(),x.b) - compress.begin();
        x.c = lower_bound(compress.begin(),compress.end(),x.c) - compress.begin();
    }
    sort(student.begin(),student.end(), cmp);

    dnc(0, n + _q);

    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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 1636 KB Output is correct
8 Correct 11 ms 1616 KB Output is correct
9 Correct 11 ms 1576 KB Output is correct
10 Correct 10 ms 1488 KB Output is correct
11 Correct 10 ms 1488 KB Output is correct
12 Correct 6 ms 1488 KB Output is correct
13 Correct 12 ms 1488 KB Output is correct
14 Correct 13 ms 1488 KB Output is correct
15 Correct 11 ms 1484 KB Output is correct
16 Correct 7 ms 1488 KB Output is correct
17 Correct 9 ms 1464 KB Output is correct
18 Correct 5 ms 1352 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 38216 KB Output is correct
2 Correct 468 ms 38228 KB Output is correct
3 Correct 482 ms 38196 KB Output is correct
4 Correct 401 ms 36200 KB Output is correct
5 Correct 300 ms 36012 KB Output is correct
6 Correct 214 ms 33252 KB Output is correct
7 Correct 436 ms 38076 KB Output is correct
8 Correct 472 ms 37960 KB Output is correct
9 Correct 419 ms 37720 KB Output is correct
10 Correct 261 ms 35924 KB Output is correct
11 Correct 335 ms 35992 KB Output is correct
12 Correct 212 ms 32712 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 38216 KB Output is correct
2 Correct 468 ms 38228 KB Output is correct
3 Correct 482 ms 38196 KB Output is correct
4 Correct 401 ms 36200 KB Output is correct
5 Correct 300 ms 36012 KB Output is correct
6 Correct 214 ms 33252 KB Output is correct
7 Correct 436 ms 38076 KB Output is correct
8 Correct 472 ms 37960 KB Output is correct
9 Correct 419 ms 37720 KB Output is correct
10 Correct 261 ms 35924 KB Output is correct
11 Correct 335 ms 35992 KB Output is correct
12 Correct 212 ms 32712 KB Output is correct
13 Correct 477 ms 39496 KB Output is correct
14 Correct 461 ms 39376 KB Output is correct
15 Correct 464 ms 38196 KB Output is correct
16 Correct 385 ms 37272 KB Output is correct
17 Correct 337 ms 37196 KB Output is correct
18 Correct 202 ms 33144 KB Output is correct
19 Correct 419 ms 39496 KB Output is correct
20 Correct 488 ms 39508 KB Output is correct
21 Correct 456 ms 39252 KB Output is correct
22 Correct 249 ms 35844 KB Output is correct
23 Correct 340 ms 35776 KB Output is correct
24 Correct 182 ms 32868 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 1636 KB Output is correct
8 Correct 11 ms 1616 KB Output is correct
9 Correct 11 ms 1576 KB Output is correct
10 Correct 10 ms 1488 KB Output is correct
11 Correct 10 ms 1488 KB Output is correct
12 Correct 6 ms 1488 KB Output is correct
13 Correct 12 ms 1488 KB Output is correct
14 Correct 13 ms 1488 KB Output is correct
15 Correct 11 ms 1484 KB Output is correct
16 Correct 7 ms 1488 KB Output is correct
17 Correct 9 ms 1464 KB Output is correct
18 Correct 5 ms 1352 KB Output is correct
19 Correct 473 ms 38216 KB Output is correct
20 Correct 468 ms 38228 KB Output is correct
21 Correct 482 ms 38196 KB Output is correct
22 Correct 401 ms 36200 KB Output is correct
23 Correct 300 ms 36012 KB Output is correct
24 Correct 214 ms 33252 KB Output is correct
25 Correct 436 ms 38076 KB Output is correct
26 Correct 472 ms 37960 KB Output is correct
27 Correct 419 ms 37720 KB Output is correct
28 Correct 261 ms 35924 KB Output is correct
29 Correct 335 ms 35992 KB Output is correct
30 Correct 212 ms 32712 KB Output is correct
31 Correct 477 ms 39496 KB Output is correct
32 Correct 461 ms 39376 KB Output is correct
33 Correct 464 ms 38196 KB Output is correct
34 Correct 385 ms 37272 KB Output is correct
35 Correct 337 ms 37196 KB Output is correct
36 Correct 202 ms 33144 KB Output is correct
37 Correct 419 ms 39496 KB Output is correct
38 Correct 488 ms 39508 KB Output is correct
39 Correct 456 ms 39252 KB Output is correct
40 Correct 249 ms 35844 KB Output is correct
41 Correct 340 ms 35776 KB Output is correct
42 Correct 182 ms 32868 KB Output is correct
43 Correct 489 ms 41456 KB Output is correct
44 Correct 517 ms 41300 KB Output is correct
45 Correct 485 ms 41292 KB Output is correct
46 Correct 431 ms 38384 KB Output is correct
47 Correct 363 ms 38348 KB Output is correct
48 Correct 249 ms 33464 KB Output is correct
49 Correct 531 ms 41236 KB Output is correct
50 Correct 536 ms 41284 KB Output is correct
51 Correct 575 ms 41116 KB Output is correct
52 Correct 357 ms 38124 KB Output is correct
53 Correct 374 ms 36800 KB Output is correct