Submission #131834

#	Time	Username	Problem	Language	Result	Execution time	Memory
131834		ekrem	Examination (JOI19_examination)	C++98	100 / 100	2853 ms	117496 KiB

examination

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas+son)/2)
#define oorta ((bbas+sson)/2)
#define mod 1000000007
#define inf 1000000009
#define LOGN 20
#define N 100005
#define M N * LOGN * LOGN
#define MAXN M
using namespace std;
 
typedef int ll;
typedef pair < int , int > ii;
 
int n, m, k, q, ans[N];
pair < int , ii > a[N];
pair < ii , ii > b[N];
int son1 = 1, son2, sol[MAXN], sag[MAXN], seg[MAXN], sl[MAXN], sg[MAXN], bas[MAXN], son[MAXN];
ll val[MAXN];
 
ll opr(ll X, ll Y) {
	return X + Y;
}
 
 
int ver(int k){
	if(!k)return 0;
	if(!seg[k]){
		son2++;
		bas[son2] = 1;
		son[son2] = m;
		return seg[k] = son2;
	}
	else
		return seg[k];
}

int yeniver(int bs, int sn){
	++son2;
	bas[son2]=bs;
	son[son2]=sn;
	return son2;
}
 
int slver(int k){
	return (!sl[k])?sl[k] = ++son2:sl[k];
}
 
int sgver(int k){
	return (!sg[k])?sg[k] = ++son2:sg[k];
}
 
int solver(int k){
	return (!sol[k])?sol[k] = ++son1:sol[k];
}
 
int sagver(int k){
	return (!sag[k])?sag[k] = ++son1:sag[k];
}
 
ll qu2(int k, int x, int y){
	if(!k or bas[k] > y or son[k] < x)
		return 0;
	if(bas[k] >= x and son[k] <= y)
		return val[k];
	return opr(qu2(sl[k], x, y), qu2(sg[k], x, y));
}
 
ll qu1(int k, int bas, int son, int x, int y, int xx, int yy){
	if(!k or bas > y or son < x)
		return 0;
	if(bas >= x and son <= y)
		return qu2(seg[k], xx, yy);
	return opr(qu1(sol[k], bas, orta, x, y, xx, yy), qu1(sag[k], orta + 1, son, x, y, xx, yy));
}
 
void up2(int k, int x, ll z){
	if(bas[k] == son[k]){
		val[k] += z;
		return;
	}
	int git = (x <= ((bas[k]+son[k])/2)) ? sl[k] : sg[k];
	if(!git){
		int of = ((x <= ((bas[k]+son[k])/2)) ? sl[k] : sg[k]) = yeniver(x, x);
		val[of] += z;
	}
	else if(bas[git] <= x and son[git] >= x)
			up2(git, x, z);
	else{
		int	bbas = bas[k], sson = son[k];
		do{
			if(x <= oorta)
				sson = oorta;
			else
				bbas = oorta + 1;
		}while((x <= oorta) == (bas[git] <= oorta) );
		int of = ((x <= ((bas[k]+son[k])/2)) ? sl[k] : sg[k]) = yeniver(bbas, sson);
		(bas[git] <= oorta ? sl[of] : sg[of]) = git;
		up2(of, x, z);
	}
	val[k] = opr(val[sl[k]], val[sg[k]]);
}
 
void up1(int k, int bas, int son, int x, int y, ll z){
	if(bas == son){
		up2(ver(k), y, z);
		return;
	}
	if(x <= orta)
		up1(solver(k), bas, orta, x, y, z);
	else
		up1(sagver(k), orta + 1, son, x, y, z);
	up2(ver(k), y, z);
}

map < int , int > h, hh, x, xx;
map < int , int > :: iterator it;
 
int main(){
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d",&k ,&q);
	for(int i = 1; i <= k; i++){
		scanf("%d %d",&a[i].nd.st ,&a[i].nd.nd);
		a[i].st = a[i].nd.st + a[i].nd.nd;
		h[a[i].nd.st] = 1;
		hh[a[i].nd.nd] = 1;
	}
	sort(a + 1, a + k + 1);
	for(int i = 1; i <= q; i++){
		scanf("%d %d %d" ,&b[i].nd.st ,&b[i].nd.nd,&b[i].st.st);
		h[b[i].nd.st] = 1;
		hh[b[i].nd.nd] = 1;
		b[i].st.nd = i;
	}
	for(it = h.begin(); it != h.end(); it++)
		x[it->st] = ++n;
 
	for(it = hh.begin(); it != hh.end(); it++)
		xx[it->st] = ++m;
	// cout << n << " " << m << endl;
	sort(b + 1, b + q + 1);
	reverse(b + 1, b + q + 1);
	for(int i = 1; i <= q; i++){
		while(k >= 1 and a[k].st >= b[i].st.st){
			// cout << ne[a[k].nd.st] << " " << nee[a[k].nd.nd] << " geldi" << endl << endl;
			// cout << x[a[k].nd.st] << " " << xx[a[k].nd.nd] << " geldi" << endl;
			// int of = qu1(1, 1, n, x[a[k].nd.st],x[a[k].nd.st], xx[a[k].nd.nd],xx[a[k].nd.nd]);
			up1(1, 1, n, x[a[k].nd.st], xx[a[k].nd.nd], 1);
			k--;
		}
		// cout << b[i].st.nd << " icin bul " << n << " " << m << endl;
		// cout << x[b[i].nd.st] << " " << xx[b[i].nd.nd] << endl;
		ans[b[i].st.nd] = qu1(1, 1, n, x[b[i].nd.st], n, xx[b[i].nd.nd], m );
	}
	for(int i = 1; i <= q; i++)
		printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&k ,&q);
  ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].nd.st ,&a[i].nd.nd);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d" ,&b[i].nd.st ,&b[i].nd.nd,&b[i].st.st);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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