oj.uz

Submission #375087

# Submission time Handle Problem Language Result Execution time Memory
375087 2021-03-09T02:27:48 Z jass921026 Examination (JOI19_examination) C++14
20 / 100
 164 ms 11604 KB 
#include<bits/stdc++.h>
using namespace std;
#define jizz ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ALL(x) (x).begin(),(x).end()
const int MAXN=1E5+10;
struct student{
    int type, a, b, c, id;
    student(int t, int a, int b, int c, int id):type(t),a(a),b(b),c(c),id(id){};
};
bool cmp(student x, student y){
    if(x.a==y.a) return x.type<y.type;
    return x.a>y.a;
}
int n, q, ans[MAXN];
vector<student> v;
struct node{
    int val;
    node* left=NULL;
    node* right=NULL;
    void pull(){
        val=left->val+right->val;
    }
    node(int v):val(v){};
    node(node* a, node* b){
        left=a, right=b;
        pull();
    }
};
node* root;
struct segment_tree{
    node* init(int l=0, int r=MAXN){
        if(l==r) return new node(0);
        int mid=(l+r)/2;
        return new node(init(l,mid),init(mid+1,r));
    }
    void modify(int pos, int val, node* now=root, int l=0, int r=MAXN){
        if(l==r){
            now->val+=val;
            return;
        }
        int mid=(l+r)/2;
        if(pos<=mid){
            modify(pos,val,now->left,l,mid);
        } else{
            modify(pos,val,now->right,mid+1,r);
        }
        now->pull();
    }
    int query(int ql, int qr, node* now=root, int l=0, int r=MAXN){
        if(r<ql||l>qr) return 0;
        if(ql<=l&&r<=qr) return now->val;
        int mid=(l+r)/2;
        return query(ql,qr,now->left,l,mid)+query(ql,qr,now->right,mid+1,r);
    }
} sgt;
int main(){ jizz
    cin>>n>>q;
    for(int i=0;i<n;i++){
        int s, t;
        cin>>s>>t;
        v.push_back(student(0,s,t,s+t,i));
    }
    for(int i=0;i<q;i++){
        int x, y, z;
        cin>>x>>y>>z;
        v.push_back(student(1,x,y,z,i));
    }
    sort(ALL(v),cmp);
    root=sgt.init();
    for(int i=0;i<n+q;i++){
        //cout<<v[i].type<<" "<<v[i].a<<" "<<v[i].b<<"\n";
        if(v[i].type==0){
            sgt.modify(v[i].b,1);
        } else{
            ans[v[i].id]=sgt.query(v[i].b,MAXN);
        }
    }
    for(int i=0;i<q;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}
/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
*/
/*
10 10
41304 98327
91921 28251
85635 59191
30361 72671
28949 96958
99041 37826
10245 2726
19387 20282
60366 87723
95388 49726
52302 69501 66009
43754 45346 3158
25224 58881 18727
7298 24412 63782
24107 10583 61508
65025 29140 7278
36104 56758 2775
23126 67608 122051
56910 17272 62933
39675 15874 117117
*/

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 6636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 11476 KB Output is correct
2 Correct 164 ms 11564 KB Output is correct
3 Correct 160 ms 11476 KB Output is correct
4 Correct 117 ms 11476 KB Output is correct
5 Correct 140 ms 11476 KB Output is correct
6 Correct 102 ms 11476 KB Output is correct
7 Correct 154 ms 11476 KB Output is correct
8 Correct 153 ms 11476 KB Output is correct
9 Correct 143 ms 11476 KB Output is correct
10 Correct 136 ms 11492 KB Output is correct
11 Correct 113 ms 11348 KB Output is correct
12 Correct 93 ms 11092 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 11476 KB Output is correct
2 Correct 164 ms 11564 KB Output is correct
3 Correct 160 ms 11476 KB Output is correct
4 Correct 117 ms 11476 KB Output is correct
5 Correct 140 ms 11476 KB Output is correct
6 Correct 102 ms 11476 KB Output is correct
7 Correct 154 ms 11476 KB Output is correct
8 Correct 153 ms 11476 KB Output is correct
9 Correct 143 ms 11476 KB Output is correct
10 Correct 136 ms 11492 KB Output is correct
11 Correct 113 ms 11348 KB Output is correct
12 Correct 93 ms 11092 KB Output is correct
13 Incorrect 163 ms 11604 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 6636 KB Output isn't correct
2 Halted 0 ms 0 KB -