Submission #1041997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041997		1L1YA	Examination (JOI19_examination)	C++17	100 / 100	629 ms	91568 KiB

examination

//1L1YA

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

//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define Pb              push_back
#define F               first
#define S               second
#define endl            '\n'
#define sep             ' '
#define all(x)          x.begin(),x.end()
#define al(x,n)         x+1,x+n+1
#define SZ(x)           ((int)x.size())
#define lc              (id<<1)
#define rc              (lc|1)
#define mid             (l+r>>1)
#define dokme(x)        cout << x << endl, exit(0)
#define sik(x)          cout << x << endl;continue;
#define FastIO          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll oo=1e18;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=2e5+11;
const int lg=23;

int n,m,q,a[N],b[N],x[N],y[N],z[N],ans[N];
vector<pii> Q,vec;
vector<int> comp;
struct node{
	vector<int> vc,fen;
}seg[N<<2];

void upd(int id,int x,int y){
	int sz=SZ(seg[id].vc);
	for(x=sz-x;x<=sz;x+=x&-x)	seg[id].fen[x]+=y;
}

int gett(int id,int x){
	int sz=SZ(seg[id].vc),ans=0;
	for(x=sz-x;x;x-=x&-x)	ans+=seg[id].fen[x];
	return ans;
}

void build1(int pos,int val,int id=1,int l=0,int r=m){
	seg[id].vc.Pb(val);
	if(r-l==1)	return;
	if(pos<mid)	build1(pos,val,lc,l,mid);
	else	build1(pos,val,rc,mid,r);
}

void build2(int ql,int qr,int val,int id=1,int l=0,int r=m){
	if(qr<=l || ql>=r)	return;
	if(ql<=l && r<=qr){
		seg[id].vc.Pb(val);
		return;
	}
	build2(ql,qr,val,lc,l,mid);
	build2(ql,qr,val,rc,mid,r);
}

void build(int id=1,int l=0,int r=m){
	sort(all(seg[id].vc));
	seg[id].vc.resize(unique(all(seg[id].vc))-seg[id].vc.begin());
	seg[id].fen.resize(SZ(seg[id].vc)+1);
	if(r-l==1)	return;
	build(lc,l,mid);
	build(rc,mid,r);
}

void modify(int pos,int val,int id=1,int l=0,int r=m){
	upd(id,lower_bound(all(seg[id].vc),val)-seg[id].vc.begin(),1);
	if(r-l==1)	return;
	if(pos<mid)	modify(pos,val,lc,l,mid);
	else	modify(pos,val,rc,mid,r);
}

int get(int ql,int qr,int val,int id=1,int l=0,int r=m){
	if(qr<=l || ql>=r)	return 0;
	if(ql<=l && r<=qr)	return gett(id,lower_bound(all(seg[id].vc),val)-seg[id].vc.begin());
	return get(ql,qr,val,lc,l,mid)+get(ql,qr,val,rc,mid,r);
}

int main(){
	FastIO

	cin >> n >> q;
	for(int i=1;i<=n;i++){
		cin >> a[i] >> b[i];
		comp.Pb(b[i]);
		vec.Pb({a[i],i});
	}
	for(int i=1;i<=q;i++){
		cin >> x[i] >> y[i] >> z[i];
		comp.Pb(y[i]);
		Q.Pb({x[i],i});
	}
	sort(all(Q));
	sort(all(vec),greater<>());
	sort(all(comp));
	comp.resize(unique(all(comp))-comp.begin());
	m=SZ(comp);
	for(int i=1;i<=n;i++)	b[i]=lower_bound(all(comp),b[i])-comp.begin(),build1(b[i],a[i]+comp[b[i]]);
	for(int i=1;i<=q;i++)	y[i]=lower_bound(all(comp),y[i])-comp.begin(),build2(y[i],m,z[i]);
	build();
	for(auto [x,i]: vec){
		while(SZ(Q) && Q.back().F>x){
			int j=Q.back().S;Q.pop_back();
			ans[j]=get(y[j],m,z[j]);
		}
		modify(b[i],a[i]+comp[b[i]]);
	}
	while(SZ(Q)){
		int j=Q.back().S;Q.pop_back();
		ans[j]=get(y[j],m,z[j]);
	}
	for(int i=1;i<=q;i++)	cout << ans[i] << endl;

	return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void build1(int, int, int, int, int)':
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:58:9: note: in expansion of macro 'mid'
   58 |  if(pos<mid) build1(pos,val,lc,l,mid);
      |         ^~~
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:58:34: note: in expansion of macro 'mid'
   58 |  if(pos<mid) build1(pos,val,lc,l,mid);
      |                                  ^~~
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:59:25: note: in expansion of macro 'mid'
   59 |  else build1(pos,val,rc,mid,r);
      |                         ^~~
examination.cpp: In function 'void build2(int, int, int, int, int, int)':
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:68:24: note: in expansion of macro 'mid'
   68 |  build2(ql,qr,val,lc,l,mid);
      |                        ^~~
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:69:22: note: in expansion of macro 'mid'
   69 |  build2(ql,qr,val,rc,mid,r);
      |                      ^~~
examination.cpp: In function 'void build(int, int, int)':
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:77:13: note: in expansion of macro 'mid'
   77 |  build(lc,l,mid);
      |             ^~~
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:78:11: note: in expansion of macro 'mid'
   78 |  build(rc,mid,r);
      |           ^~~
examination.cpp: In function 'void modify(int, int, int, int, int)':
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:84:9: note: in expansion of macro 'mid'
   84 |  if(pos<mid) modify(pos,val,lc,l,mid);
      |         ^~~
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:84:34: note: in expansion of macro 'mid'
   84 |  if(pos<mid) modify(pos,val,lc,l,mid);
      |                                  ^~~
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:85:25: note: in expansion of macro 'mid'
   85 |  else modify(pos,val,rc,mid,r);
      |                         ^~~
examination.cpp: In function 'int get(int, int, int, int, int, int)':
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:91:28: note: in expansion of macro 'mid'
   91 |  return get(ql,qr,val,lc,l,mid)+get(ql,qr,val,rc,mid,r);
      |                            ^~~
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:91:50: note: in expansion of macro 'mid'
   91 |  return get(ql,qr,val,lc,l,mid)+get(ql,qr,val,rc,mid,r);
      |                                                  ^~~

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