oj.uz

Submission #971892

# Submission time Handle Problem Language Result Execution time Memory
971892 2024-04-29T12:51:14 Z parlimoos Examination (JOI19_examination) C++14
100 / 100
 1124 ms 258708 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n , q;
vector<arr(3)> a;
vector<int> seg[3][2400001] , cmp;
vector<arr(4)> ops;
int seginf[2400001][2] , is[600000];

void cmpInt(){
    sort(cmp.bg() , cmp.end());
    cmp.resize(int(unique(cmp.bg() , cmp.end()) - cmp.bg()));

    for(auto &el : a){
        el[0] = int(lb(cmp.bg() , cmp.end() , el[0]) - cmp.bg());
        el[1] = int(lb(cmp.bg() , cmp.end() , el[1]) - cmp.bg());
        el[2] = int(lb(cmp.bg() , cmp.end() , el[2]) - cmp.bg());
    }
    for(auto &op : ops){
        op[0] = int(lb(cmp.bg() , cmp.end() , op[0]) - cmp.bg());
        op[1] = int(lb(cmp.bg() , cmp.end() , op[1]) - cmp.bg());
        op[2] = int(lb(cmp.bg() , cmp.end() , op[2]) - cmp.bg());
    }
}
void buildSeg(int l = 0 , int r = int(6e5) - 1 , int i = 1){
    seginf[i][0] = l , seginf[i][1] = r;
    if(l == r) is[l] = i;
    else{
        int c = (r + l - 1) >> 1;
        buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
    }
}
void addSeg(int md , int i , int val){
    while(i >= 1) seg[md][i].pb(val) , i >>= 1;
}
void drawSeg(){
    for(int j = 0 ; j < 3 ; j++) for(int i = 1 ; i < int(2400001) ; i++) sort(seg[j][i].bg() , seg[j][i].end());
}
int getSeg(int l , int r , int md , int i , int x , int y){
    if(seginf[i][0] >= l and seginf[i][1] <= r){
        if(md == 0){
            return int(seg[0][i].size()) - int(lb(seg[0][i].bg() , seg[0][i].end() , x) - seg[0][i].bg());
        }
        int res = int(seg[1][i].size());
        res -= int(lb(seg[1][i].bg() , seg[1][i].end() , x) - seg[1][i].bg());
        res -= int(lb(seg[2][i].bg() , seg[2][i].end() , y) - seg[2][i].bg());
        return res;
    }
    if(seginf[i][1] >= l and seginf[i][0] <= r){
        return getSeg(l , r , md , i << 1 , x , y) + getSeg(l , r , md , (i << 1) | 1 , x , y);
    }
    return 0;
}

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

    cin >> n >> q;
    for(int i = 0 ; i < n ; i++){
        arr(2) d;
        cin >> d[0] >> d[1];
        a.pb({d[0] , d[1] , d[0] + d[1]}) , cmp.pb(d[0]) , cmp.pb(d[1]) , cmp.pb(d[0] + d[1]);
    }
    for(int i = 0 ; i < q ; i++){
        int x , y , z;
        cin >> x >> y >> z;
        ops.pb({x , y , z , int(z <= x + y)}) , cmp.pb(x) , cmp.pb(y) , cmp.pb(z);
    }
    cmpInt() , buildSeg();
    for(int i = 0 ; i < n ; i++){
        addSeg(0 , is[a[i][0]] , a[i][1]);
        addSeg(1 , is[a[i][2]] , a[i][0]) , addSeg(2 , is[a[i][2]] , a[i][1]);
    }
    drawSeg();
    for(int i = 0 ; i < q ; i++){
        if(ops[i][3]) cout << getSeg(ops[i][0] , 600000 - 1 , 0 , 1 , ops[i][1] , -1) << endl;
        else cout << getSeg(ops[i][2] , 600000 - 1 , 1 , 1 , ops[i][0] , ops[i][1]) << endl;
    }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 188500 KB Output is correct
2 Correct 85 ms 188732 KB Output is correct
3 Correct 85 ms 188500 KB Output is correct
4 Correct 87 ms 188868 KB Output is correct
5 Correct 85 ms 188684 KB Output is correct
6 Correct 85 ms 188688 KB Output is correct
7 Correct 102 ms 190644 KB Output is correct
8 Correct 105 ms 190652 KB Output is correct
9 Correct 101 ms 190476 KB Output is correct
10 Correct 101 ms 190548 KB Output is correct
11 Correct 106 ms 190536 KB Output is correct
12 Correct 94 ms 189912 KB Output is correct
13 Correct 104 ms 190560 KB Output is correct
14 Correct 100 ms 190544 KB Output is correct
15 Correct 99 ms 190548 KB Output is correct
16 Correct 95 ms 190288 KB Output is correct
17 Correct 101 ms 190568 KB Output is correct
18 Correct 95 ms 189936 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 837 ms 236128 KB Output is correct
2 Correct 834 ms 236060 KB Output is correct
3 Correct 829 ms 236416 KB Output is correct
4 Correct 683 ms 236484 KB Output is correct
5 Correct 631 ms 231432 KB Output is correct
6 Correct 306 ms 223164 KB Output is correct
7 Correct 797 ms 236104 KB Output is correct
8 Correct 784 ms 235972 KB Output is correct
9 Correct 767 ms 235864 KB Output is correct
10 Correct 537 ms 229800 KB Output is correct
11 Correct 600 ms 234684 KB Output is correct
12 Correct 218 ms 223164 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 837 ms 236128 KB Output is correct
2 Correct 834 ms 236060 KB Output is correct
3 Correct 829 ms 236416 KB Output is correct
4 Correct 683 ms 236484 KB Output is correct
5 Correct 631 ms 231432 KB Output is correct
6 Correct 306 ms 223164 KB Output is correct
7 Correct 797 ms 236104 KB Output is correct
8 Correct 784 ms 235972 KB Output is correct
9 Correct 767 ms 235864 KB Output is correct
10 Correct 537 ms 229800 KB Output is correct
11 Correct 600 ms 234684 KB Output is correct
12 Correct 218 ms 223164 KB Output is correct
13 Correct 891 ms 237280 KB Output is correct
14 Correct 887 ms 238964 KB Output is correct
15 Correct 859 ms 238664 KB Output is correct
16 Correct 758 ms 239032 KB Output is correct
17 Correct 805 ms 234052 KB Output is correct
18 Correct 367 ms 224036 KB Output is correct
19 Correct 953 ms 240460 KB Output is correct
20 Correct 943 ms 239976 KB Output is correct
21 Correct 961 ms 240208 KB Output is correct
22 Correct 620 ms 231912 KB Output is correct
23 Correct 631 ms 237444 KB Output is correct
24 Correct 194 ms 223808 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 188500 KB Output is correct
2 Correct 85 ms 188732 KB Output is correct
3 Correct 85 ms 188500 KB Output is correct
4 Correct 87 ms 188868 KB Output is correct
5 Correct 85 ms 188684 KB Output is correct
6 Correct 85 ms 188688 KB Output is correct
7 Correct 102 ms 190644 KB Output is correct
8 Correct 105 ms 190652 KB Output is correct
9 Correct 101 ms 190476 KB Output is correct
10 Correct 101 ms 190548 KB Output is correct
11 Correct 106 ms 190536 KB Output is correct
12 Correct 94 ms 189912 KB Output is correct
13 Correct 104 ms 190560 KB Output is correct
14 Correct 100 ms 190544 KB Output is correct
15 Correct 99 ms 190548 KB Output is correct
16 Correct 95 ms 190288 KB Output is correct
17 Correct 101 ms 190568 KB Output is correct
18 Correct 95 ms 189936 KB Output is correct
19 Correct 837 ms 236128 KB Output is correct
20 Correct 834 ms 236060 KB Output is correct
21 Correct 829 ms 236416 KB Output is correct
22 Correct 683 ms 236484 KB Output is correct
23 Correct 631 ms 231432 KB Output is correct
24 Correct 306 ms 223164 KB Output is correct
25 Correct 797 ms 236104 KB Output is correct
26 Correct 784 ms 235972 KB Output is correct
27 Correct 767 ms 235864 KB Output is correct
28 Correct 537 ms 229800 KB Output is correct
29 Correct 600 ms 234684 KB Output is correct
30 Correct 218 ms 223164 KB Output is correct
31 Correct 891 ms 237280 KB Output is correct
32 Correct 887 ms 238964 KB Output is correct
33 Correct 859 ms 238664 KB Output is correct
34 Correct 758 ms 239032 KB Output is correct
35 Correct 805 ms 234052 KB Output is correct
36 Correct 367 ms 224036 KB Output is correct
37 Correct 953 ms 240460 KB Output is correct
38 Correct 943 ms 239976 KB Output is correct
39 Correct 961 ms 240208 KB Output is correct
40 Correct 620 ms 231912 KB Output is correct
41 Correct 631 ms 237444 KB Output is correct
42 Correct 194 ms 223808 KB Output is correct
43 Correct 1123 ms 255396 KB Output is correct
44 Correct 1124 ms 256980 KB Output is correct
45 Correct 1112 ms 255728 KB Output is correct
46 Correct 1039 ms 258708 KB Output is correct
47 Correct 830 ms 247168 KB Output is correct
48 Correct 312 ms 225720 KB Output is correct
49 Correct 1076 ms 256344 KB Output is correct
50 Correct 1094 ms 255168 KB Output is correct
51 Correct 1055 ms 255720 KB Output is correct
52 Correct 734 ms 242388 KB Output is correct
53 Correct 702 ms 249848 KB Output is correct