Submission #1290088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290088		jojeonghoon	Examination (JOI19_examination)	C++20	100 / 100	2369 ms	18196 KiB

examination

#include <iostream>
#include <vector>
#include <set>
#include<algorithm>
#include<queue>
#include<map>
#include<math.h>
#include<assert.h>
#define ll long long
#define int ll
#define db double
#define pii pair<int,int>
#define bk back()
using namespace std;

const int LM=100100, Bu=300;
int N,Q, ans[LM];
int S[LM],T[LM];
struct Query{
    int x,y,z, num;
    bool operator<(const Query&r)const{
        return x<r.x;
    }
}q[LM];

struct Data{
    int x, y, num;
}A[LM], xs[LM], ys[LM], xys[LM];
int pw[LM],xyx[LM], w[LM];

void update(int x, int v){
    for(int i=x; i<=N; i+=i&-i) pw[i]+=v;
}

int Sum(int l, int r){
    int ret=0;
    for(int i=l-1; i>0; i-=i&-i) ret -= pw[i];
    for(int i=r;   i>0; i-=i&-i) ret += pw[i];
    return ret;
}

bool comp1(const Data &a, const Data &b){return a.x<b.x;}
bool comp2(const Data &a, const Data &b){return a.y<b.y;}
bool comp3(const Data &a, const Data &b){
    return a.x+a.y==b.x+b.y ? a.num<b.num : a.x+a.y<b.x+b.y;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>Q;
    for(int i=1; i<=N; i++){
        cin>>S[i]>>T[i];
        A[i] = {S[i],T[i], i};
        xs[i]=A[i];
        ys[i]=A[i];
        xys[i]=A[i];
    }
    for(int i=1; i<=Q; i++){
        cin>>q[i].x>>q[i].y>>q[i].z;
        q[i].num=i;
    }
    sort(q+1,q+Q+1);
    sort(xs+1,xs+N+1, comp1);
    sort(ys+1,ys+N+1, comp2);
    sort(xys+1,xys+N+1, comp2);
    
    for(int i=1; i<=N; i+=Bu){
        sort(xys+i, xys+min(i+Bu,N+1),comp3);
    }
    
    for(int i=1; i<=N; i++){
        xyx[xys[i].num]=i;
        update(i, 1);
        w[i]=1;
    }
    
    int xp=1;
    
    for(int i=1; i<=Q; i++){
        int A=q[i].x, B=q[i].y, C=q[i].z, ANS=0;
        for(; xp<=N && xs[xp].x<A; xp++) update( xyx[xs[xp].num], -1 ), w[xs[xp].num]=0;
        
        for(int i=1; i<=N; i+=Bu){
            if(i+Bu<=N && ys[i+Bu].y < B) continue;
            
            if(ys[i].y < B){
                for(; i<=N && ys[i].y<B; i++);
                for(; (i-1)%Bu!=0 && i<=N; i++){
                    ANS += w[ys[i].num] * (ys[i].x+ys[i].y >= C);
                }
            }
            if(i>N) break;
            
            int l = lower_bound(xys+i, xys+min(i+Bu, N+1), (Data){C,0,0}, comp3) -xys, r=min(i+Bu-1, N);
            
            ANS += Sum(l,r);
        }
        
        ans[q[i].num] = ANS;
    }
    
    for(int i=1; i<=Q; i++) cout<<ans[i]<<'\n';
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57