Submission #131681

#	Time	Username	Problem	Language	Result	Execution time	Memory
131681		ekrem	Examination (JOI19_examination)	C++98	43 / 100	3037 ms	290636 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 mod 1000000007
#define inf 1000000009
#define LOGN 30
#define N 100005
#define M N * LOGN * LOGN
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;

int n, m, k, q, say1 = 1, say2, seg1[N * LOGN], sol1[N * LOGN], sag1[N * LOGN], seg2[M], sol2[M], sag2[M],  bs[M], sn[M], ans[N];
pair < int , ii > a[N];
pair < ii , ii > b[N];

int ver(int k){return seg1[k] = (!seg1[k])?++say2:seg1[k];}
int solver1(int k){return sol1[k] = (!sol1[k])?++say1:sol1[k];}
int sagver1(int k){return sag1[k] = (!sag1[k])?++say1:sag1[k];}
int solver2(int k){return sol2[k] = (!sol2[k])?++say2:sol2[k];}
int sagver2(int k){return sag2[k] = (!sag2[k])?++say2:sag2[k];}

void up2(int k, int bas, int son, int x){
	if(bas == son){
		seg2[k]++;
		return;
	}
	if(x <= orta)
		up2(solver2(k), bas, orta, x);
	else
		up2(sagver2(k), orta + 1, son, x);
	seg2[k] = seg2[sol2[k]] + seg2[sag2[k]];
}

void up1(int k, int bas, int son, int x, int y){
	if(bas == son){
		up2(ver(k), 1, m, y);
		// cout << bas << " " << son << " " << ver(k) << " a " << y << " artti" << endl;
		return;
	}
	if(x <= orta)
		up1(solver1(k), bas, orta, x, y);
	else
		up1(sagver1(k), orta + 1, son, x, y);
	// cout << bas << " " << son << " " << ver(k) << " a " << y << " artti" << endl;
	up2(ver(k), 1, m, y);
}

int qu2(int k, int bas, int son, int x){
	if(!k or son < x)
		return 0;
	if(bas >= x)
		return seg2[k];
	return qu2(sol2[k], bas, orta, x) + qu2(sag2[k], orta + 1, son, x);
}

int qu1(int k, int bas, int son, int x, int y){
	if(!k or son < x)
		return 0;
	if(bas >= x){
		// cout << bas << " " << son << " " << seg1[k] << " " << y << " = " << qu2(seg1[k], 1, m, y) << endl;
		return qu2(seg1[k], 1, m, y);
	}
	return qu1(sol1[k], bas, orta, x, y) + qu1(sag1[k], orta + 1, son, x, y);
}

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;
			up1(1, 1, n, x[a[k].nd.st], xx[a[k].nd.nd]);
			k--;
		}
		// cout << b[i].st.nd << " icin bul " << n << " " << m << endl;
		ans[b[i].st.nd] = qu1(1, 1, n, x[b[i].nd.st], xx[b[i].nd.nd] );
	}
	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:77: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:79: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:86: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: 0 / 57