oj.uz

Submission #971891

# Submission time Handle Problem Language Result Execution time Memory
971891 2024-04-29T12:49:04 Z parlimoos Examination (JOI19_examination) C++14
20 / 100
 911 ms 240164 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(ub(seg[1][i].bg() , seg[1][i].end() , x) - seg[1][i].bg());
        res -= int(ub(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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 188500 KB Output is correct
2 Correct 88 ms 188508 KB Output is correct
3 Correct 87 ms 188496 KB Output is correct
4 Correct 86 ms 188732 KB Output is correct
5 Correct 86 ms 188484 KB Output is correct
6 Correct 85 ms 188732 KB Output is correct
7 Correct 107 ms 190784 KB Output is correct
8 Correct 111 ms 190804 KB Output is correct
9 Correct 103 ms 190660 KB Output is correct
10 Incorrect 107 ms 190852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 814 ms 238424 KB Output is correct
2 Correct 815 ms 238348 KB Output is correct
3 Correct 815 ms 238572 KB Output is correct
4 Correct 669 ms 238000 KB Output is correct
5 Correct 613 ms 233124 KB Output is correct
6 Correct 312 ms 223944 KB Output is correct
7 Correct 824 ms 238284 KB Output is correct
8 Correct 802 ms 238264 KB Output is correct
9 Correct 818 ms 238144 KB Output is correct
10 Correct 558 ms 231716 KB Output is correct
11 Correct 608 ms 236220 KB Output is correct
12 Correct 209 ms 223936 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 814 ms 238424 KB Output is correct
2 Correct 815 ms 238348 KB Output is correct
3 Correct 815 ms 238572 KB Output is correct
4 Correct 669 ms 238000 KB Output is correct
5 Correct 613 ms 233124 KB Output is correct
6 Correct 312 ms 223944 KB Output is correct
7 Correct 824 ms 238284 KB Output is correct
8 Correct 802 ms 238264 KB Output is correct
9 Correct 818 ms 238144 KB Output is correct
10 Correct 558 ms 231716 KB Output is correct
11 Correct 608 ms 236220 KB Output is correct
12 Correct 209 ms 223936 KB Output is correct
13 Incorrect 911 ms 240164 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 188500 KB Output is correct
2 Correct 88 ms 188508 KB Output is correct
3 Correct 87 ms 188496 KB Output is correct
4 Correct 86 ms 188732 KB Output is correct
5 Correct 86 ms 188484 KB Output is correct
6 Correct 85 ms 188732 KB Output is correct
7 Correct 107 ms 190784 KB Output is correct
8 Correct 111 ms 190804 KB Output is correct
9 Correct 103 ms 190660 KB Output is correct
10 Incorrect 107 ms 190852 KB Output isn't correct
11 Halted 0 ms 0 KB -