Submission #1249265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249265		ender_shayan	Examination (JOI19_examination)	C++20	100 / 100	218 ms	44444 KiB

examination

#include<bits/stdc++.h>
using namespace std;


typedef long long        ll;
typedef pair<int,int>    pii;
typedef pair<ll,ll>      pll;


#define F               first
#define S               second    
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x)          x.begin(),x.end()
#define pb              push_back
#define Mp              make_pair
#define for1(n)         for(int i=1;i<=n;i++)
#define for0(n)         for(int i=0;i<n;i++)
#define set_dec(x)	    cout << fixed << setprecision(x);
#define endl            '\n'
#define lb              lower_bound


const int N=1e5+10;

int n,m,k,q,ans[N];
vector<int>vec;
vector<pii>ad[N*6];
vector<pair<pii,int>>Q[N*6];
pii A[N];
pair<pii,int>B[N];
int fen[2][N*6],num;
int gt(int x){
    return lb(all(vec),x)-vec.begin();
}
void upd(int i,int x,int t){
    for(;i<N*6;i+=i&-i)fen[t][i]+=x;
}
int get(int i,int t){
    int ans=0;
    for(;i>0;i-=i&-i)ans+=fen[t][i];
    return ans;
}
int main(){
    fast_io
    vec.pb(-1);
    cin>>n>>m;
    for1(n){
        int x,y;cin>>x>>y;
        A[i]={x,y};
        vec.pb(x);vec.pb(y);
        vec.pb(x+y);
    }
    for1(m){
        int a,b,c;cin>>a>>b>>c;
        c=max(c,a+b);
        B[i]={{a,b},c};
        vec.pb(a);vec.pb(b);
        vec.pb(c);
    }
    sort(all(vec));vec.resize(unique(all(vec))-vec.begin());
    for1(n)
        ad[gt(A[i].F+A[i].S)].pb({gt(A[i].F),gt(A[i].S)});
    for1(m)Q[gt(B[i].S)].pb({{gt(B[i].F.F),gt(B[i].F.S)},i});
    for(int i=vec.size()-1;i>=1;i--){
        for(pii p:ad[i]){upd(p.F,1,0);upd(p.S,1,1);num++;}
        for(pair<pii,int>p:Q[i])
            ans[p.S]=num-get(p.F.F-1,0)-get(p.F.S-1,1);
    }
    for1(m)cout<<ans[i]<<endl;

}

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