Submission #282584

#	Time	Username	Problem	Language	Result	Execution time	Memory
282584		Dremix10	Examination (JOI19_examination)	C++17	20 / 100	132 ms	7264 KiB

examination

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
    #define p(x)
    #define p2(x,y)
    #define pp(x)
    #define pv(x)
    #define ppv(x)
#endif
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 1e18;
const int MOD = 1e9+7;
const int N = 2e5+1;

int seg[N*4];

void update(int s, int e, int idx, int k){
    if(s==e && s==k){
        seg[idx] ++;
        return;
    }
    if(s>k || e<k)return;
    int mid = (s+e)/2;
    update(s,mid,idx*2,k);
    update(mid+1,e,idx*2+1,k);
    seg[idx] = seg[idx*2] + seg[idx*2+1];
}

int sum(int s, int e, int idx, int qs, int qe){
    if(qs<=s && e<=qe)return seg[idx];
    if(s>qe || e<qs)return 0;
    int mid = (s+e)/2;
    return sum(s,mid,idx*2,qs,qe) + sum(mid+1,e,idx*2+1,qs,qe);
}

int main(){
fastio

int n,q;
cin>>n>>q;

pi arr[n];
int i;

for(i=0;i<n;i++)
    cin>>arr[i].F>>arr[i].S;

pair<pi,int> ask[q];
int temp;
for(i=0;i<q;i++){
    cin>>ask[i].F.F>>ask[i].F.S>>temp;
    ask[i].S = i;
}

sort(ask,ask+q,greater< pair<pi,int> >());
sort(arr,arr+n,greater<pi>());

ppv(arr)

int pos = 0;
int ans[q];

for(i=0;i<q;i++){
    while(pos<n && arr[pos].F >= ask[i].F.F){
        update(0,N,1,arr[pos].S);
        pos++;
    }
    ans[ask[i].S] = sum(0,N,1,ask[i].F.S,N);
    p2(pos,ans[ask[i].S])
    p2(ask[i].F.F,ask[i].F.S)
}
for(i=0;i<q;i++)
    cout<<ans[i]<<endl;

}

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