Submission #331417

# Submission time Handle Problem Language Result Execution time Memory
331417 2020-11-28T12:05:38 Z EIMONIM Examination (JOI19_examination) C++14
2 / 100
3000 ms 963836 KB
#include <bits/stdc++.h>
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
using namespace std;
const int INF = 1e9, MOD = 1e9 + 7;

int MAXX = 0, MAXY = 0;
struct Node{
    int v=0;
    Node *lp=0, *rp=0;
    Node(){}
    void fix(){
        if (!lp) lp = new Node();
        if (!rp) rp = new Node();
    }
    void update(int i, int dx, int l, int r){
        if (r<=l) return ;
        if (l+1==r){
            v+=dx;
            return ;
        }
        int mid = (l+r)/2;
        fix();
        if (i<mid) lp->update(i,dx,l,mid);
        else rp->update(i,dx,mid,r);
        //cout<<"UPDATE1: "<<i<<" "<<l<<" "<<r<<(v - lp->v - rp->v)<<endl;
        v = lp->v + rp->v;
    }
    int query(int a, int b, int l, int r){
        if (a>r || b<l) return 0;
        //cout<<"QUERY1: "<<a<<" "<<v<<" "<<l<<" "<<r<<endl;
        if (a<=l && r<=b) return v;
        int res = 0, mid = (l+r)/2;
        if (lp) res += lp->query(a,b,l,mid);
        if (rp) res += rp->query(a,b,mid,r);
        return res;
    }
};
struct Node2d{
    Node seg;
    Node2d *lp=0, *rp=0;
    Node2d(){}
    void fix(){
        if (!lp) lp = new Node2d();
        if (!rp) rp = new Node2d();
    }
    void update(int i, int j, int dx, int l, int r){
        if (r<=l) return ;
        //cout<<"UPDATE: "<<i<<" "<<j<<" "<<l<<" "<<r<<endl;
        seg.update(j, dx, 0, MAXY);
        if (l+1==r) return ;
        int mid = (l+r)/2;
        fix();
        if (i<mid) lp->update(i,j,dx,l,mid);
        else rp->update(i,j,dx,mid,r);
    }
    int query(int ax, int bx, int ay, int by, int l, int r){
        if (ax>r || bx<l) return 0;
        if (ax<=l && r<=bx) {
            int v = seg.query(ay, by, 0, MAXY);
            //cout<<"QUERY: "<<ax<<" "<<ay<<" "<<l<<" "<<r<<" "<<v<<endl;
            return v;
        }
        int res = 0, mid = (l+r)/2;
        if (lp) res += lp->query(ax,bx,ay,by,l,mid);
        if (rp) res += rp->query(ax,bx,ay,by,mid,r);
        return res;
    }
};

bool cmp(pair<int, int> a, pair<int, int> b){
    return (a.first==b.first?a.second<b.second:a.first>b.first);
}
const int MAXN = 1e5 + 10;
int s[MAXN], t[MAXN];
int a[MAXN], b[MAXN], c[MAXN];
int ans[MAXN];
pair<int, int> vals[2*MAXN];
int32_t main(){
    ios_base::sync_with_stdio(false);
    int n,q; cin>>n>>q;
    map<int, int> convs, convt;
    loop(i,0,n){
        cin>>s[i]>>t[i];
        vals[i] = {s[i]+t[i], i};
        convs[s[i]];
        convt[t[i]];
        MAXX = max(MAXX, s[i]);
        MAXY = max(MAXY, t[i]);
    }
    loop(i,0,q){
        cin>>a[i]>>b[i]>>c[i];
        vals[i+n] = {c[i], n+i};
        convs[a[i]];
        convt[b[i]];
        MAXX = max(MAXX, a[i]);
        MAXY = max(MAXY, b[i]);
    }
    sort(vals, vals+n+q, cmp);
    MAXX++, MAXY++;
    /*int cnt = 0;
    for(auto &p:convs) p.second = cnt++;
    MAXX = cnt;
    cnt = 0;
    for(auto &p:convt) p.second = cnt++;
    MAXY = cnt;
    loop(i,0,n) s[i] = convs[s[i]], t[i] = convt[t[i]];
    loop(i,0,q) a[i] = convs[a[i]], b[i] = convt[b[i]];*/
    Node2d seg;
    loop(ind, 0, n+q){
        int i = vals[ind].second;
        //cout<<"VALS: "<<vals[ind].first<<" "<<i<<" "<<i-n<<endl;
        if (i<n){ // point
            seg.update(s[i], t[i], 1, 0, MAXX);
        }
        else{ // query
            i-=n;
            ans[i] = seg.query(a[i], MAXX, b[i], MAXY, 0, MAXX);
        }
    }
    loop(i,0,q) cout<<ans[i]<<endl;
    return 0;
}
/*
color a
cls
g++ Examination.cpp -o a & a
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100





*/

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 1004 KB Output is correct
5 Correct 2 ms 1004 KB Output is correct
6 Correct 2 ms 1004 KB Output is correct
7 Correct 280 ms 166380 KB Output is correct
8 Correct 281 ms 166380 KB Output is correct
9 Correct 293 ms 166452 KB Output is correct
10 Correct 41 ms 19948 KB Output is correct
11 Correct 40 ms 18156 KB Output is correct
12 Correct 10 ms 492 KB Output is correct
13 Correct 283 ms 166508 KB Output is correct
14 Correct 280 ms 166380 KB Output is correct
15 Correct 278 ms 166508 KB Output is correct
16 Correct 27 ms 7788 KB Output is correct
17 Correct 23 ms 9708 KB Output is correct
18 Correct 9 ms 620 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 3150 ms 963836 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 3150 ms 963836 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 1004 KB Output is correct
5 Correct 2 ms 1004 KB Output is correct
6 Correct 2 ms 1004 KB Output is correct
7 Correct 280 ms 166380 KB Output is correct
8 Correct 281 ms 166380 KB Output is correct
9 Correct 293 ms 166452 KB Output is correct
10 Correct 41 ms 19948 KB Output is correct
11 Correct 40 ms 18156 KB Output is correct
12 Correct 10 ms 492 KB Output is correct
13 Correct 283 ms 166508 KB Output is correct
14 Correct 280 ms 166380 KB Output is correct
15 Correct 278 ms 166508 KB Output is correct
16 Correct 27 ms 7788 KB Output is correct
17 Correct 23 ms 9708 KB Output is correct
18 Correct 9 ms 620 KB Output is correct
19 Execution timed out 3150 ms 963836 KB Time limit exceeded
20 Halted 0 ms 0 KB -