Submission #131637

#	Time	Username	Problem	Language	Result	Execution time	Memory
131637		ekrem	Examination (JOI19_examination)	C++98	20 / 100	1795 ms	205268 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 N 1000005
#define M 30000005
using namespace std;

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

int n = 1, m = 1, k, q, say1 = 1, say2, seg1[M], sol1[M], sag1[M], seg2[M], sol2[M], sag2[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);
}

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].nd.st++;a[i].nd.nd++;
		a[i].st = a[i].nd.st + a[i].nd.nd;
		n = max(n, a[i].nd.st);
		m = max(m, a[i].nd.nd);
	}
	n++;m++;
	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);
		b[i].nd.st++;b[i].nd.nd++;
		b[i].st.nd = i;
	}
	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 << a[k].nd.st << " " << a[k].nd.nd << " geldi" << endl << endl;
			up1(1, 1, n, a[k].nd.st, a[k].nd.nd);
			k--;
		}
		// cout << b[i].st.nd << " icin bul " << n << " " << m << endl;
		ans[b[i].st.nd] = qu1(1, 1, n, min(n, b[i].nd.st), min(m, 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:73: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:75: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:84: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: 0 / 2
• Subtask 2: 20 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57