oj.uz

Submission #676642

# Submission time Handle Problem Language Result Execution time Memory
676642 2022-12-31T14:18:39 Z browntoad Examination (JOI19_examination) C++14
0 / 100
 537 ms 34492 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i, n) for(int i=(n); i>=1; i--)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define SQ(x) (x)*(x)
#define f first
#define s second
#define pii pair<int, int>
#define endl '\n'
#define pb push_back

const ll mod = 1e9+7;
const ll maxn = 6e5+5;
const ll inf = (1ll<<60);

ll pw(ll x, ll p){
    ll ret=1;
    while(p>0){
        if (p&1){
            ret*=x;
            ret%=mod;
        }
        x*=x;
        x%=mod;
        p>>=1;
    }
    return ret;
}
ll inv(ll x){
    return pw(x, mod-2);
}
vector<int> bit(maxn);
int query(int a){
    a=maxn-a-3;
    int ret=0;
    while(a>0){
        ret+=bit[a];
        a-=(a&-a);
    }
    return ret;
}
void modify(int a, int val){
    a=maxn-a-3;
    while(a<maxn){
        bit[a]+=val;
        a+=(a&-a);
    }
}
struct point{
    bool typ; // 0 is point, 1 is query
    int x, y, w;
    int id;
};
vector<point> vc;
vector<int> sol(200005);
int n, q;
vector<point> tmp;
bool cmp(point A, point B){
    if (A.w==B.w) return A.y<B.y;
    return A.w<B.w;
}
bool cmp2(point A, point B){
    if (A.x==B.x) return A.y<B.y;
    return A.x<B.x;
}
void run(int l, int r){
    if (l>=r) return;
    if (vc[l].w==vc[r].w){
        tmp.clear();
        FOR(i, l, r+1){
            tmp.pb(vc[i]);
        }
        sort(ALL(tmp), cmp2);
        RREP(i, r-l+1){
            if (tmp[i].typ) {
                sol[tmp[i].id]+=query(tmp[i].y);
            }
            else {
                modify(tmp[i].y, 1);
            }
        }
        RREP(i, r-l+1){
            if (tmp[i].typ==0){
                modify(tmp[i].y, -1);
            }
        }
        return;
    }
    int mid = (vc[l].w+vc[r].w)>>1, pos=l-1;
    FOR(i, l, r+1){
        if (vc[i].w<=mid) pos=i;
    }
    run(l, pos);
    run(pos+1, r);
    tmp.clear();
    FOR(i, l, r+1){
        tmp.pb(vc[i]);
    }
    sort(ALL(tmp), cmp2);
    RREP(i, r-l+1){
        if (tmp[i].typ==0&&tmp[i].w>mid){
            modify(tmp[i].y, 1);
        }
        if (tmp[i].typ==1&&tmp[i].w<=mid){
            sol[tmp[i].id]+=query(tmp[i].y);
        }
    }
    RREP(i, r-l+1){
        if (tmp[i].typ==0&&tmp[i].w>mid){
            modify(tmp[i].y, -1);
        }
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>q;
    vector<int> pos;
    REP(i, n){
        int x, y; cin>>x>>y;
        vc.pb({0, x, y, x+y, i});
        pos.pb(x);
        pos.pb(y);
        pos.pb(x+y);
    }
    REP(i, q){
        int x, y, c; cin>>x>>y>>c;
        vc.pb({1, x, y, c, i+n});
        pos.pb(x);
        pos.pb(y);
        pos.pb(c);
    }
    sort(ALL(pos));
    REP(i, n){
        vc[i].x=lower_bound(ALL(pos), vc[i].x)-pos.begin()+1;
        vc[i].y=lower_bound(ALL(pos), vc[i].y)-pos.begin()+1;
        vc[i].w=lower_bound(ALL(pos), vc[i].w)-pos.begin()+1;
    }
    REP(i, q){
        vc[i+n].x=lower_bound(ALL(pos), vc[i+n].x)-pos.begin()+1;
        vc[i+n].y=lower_bound(ALL(pos), vc[i+n].y)-pos.begin()+1;
        vc[i+n].w=lower_bound(ALL(pos), vc[i+n].w)-pos.begin()+1;
    }
    sort(ALL(vc), cmp);
    run(0, n+q-1);
    FOR(i, n, n+q){
        cout<<sol[i]<<endl;
    }
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 3 ms 6484 KB Output is correct
7 Correct 16 ms 7596 KB Output is correct
8 Correct 17 ms 7600 KB Output is correct
9 Correct 17 ms 7520 KB Output is correct
10 Correct 14 ms 7472 KB Output is correct
11 Correct 17 ms 7464 KB Output is correct
12 Incorrect 10 ms 7472 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 34456 KB Output is correct
2 Incorrect 528 ms 34492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 34456 KB Output is correct
2 Incorrect 528 ms 34492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 3 ms 6484 KB Output is correct
7 Correct 16 ms 7596 KB Output is correct
8 Correct 17 ms 7600 KB Output is correct
9 Correct 17 ms 7520 KB Output is correct
10 Correct 14 ms 7472 KB Output is correct
11 Correct 17 ms 7464 KB Output is correct
12 Incorrect 10 ms 7472 KB Output isn't correct
13 Halted 0 ms 0 KB -