oj.uz

Submission #131632

# Submission time Handle Problem Language Result Execution time Memory
131632 2019-07-17T10:49:25 Z ekrem Examination (JOI19_examination) C++
0 / 100
 2296 ms 404716 KB 
#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 < ll , ll > ii;

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

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

void up2(ll k, ll bas, ll son, ll 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(ll k, ll bas, ll son, ll x, ll 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);
}

ll qu2(ll k, ll bas, ll son, ll 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);
}

ll qu1(ll k, ll bas, ll son, ll x, ll 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("%lld %lld",&k ,&q);
	for(ll i = 1; i <= k; i++){
		scanf("%lld %lld",&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(ll i = 1; i <= q; i++){
		scanf("%lld %lld %lld" ,&b[i].nd.st ,&b[i].nd.nd,&b[i].st.st);
		b[i].st.nd = i;
	}
	sort(b + 1, b + q + 1);
	reverse(b + 1, b + q + 1);
	for(ll 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(ll i = 1; i <= q; i++)
		printf("%lld\n", ans[i]);
	return 0;
}

Compilation message

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("%lld %lld",&k ,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
examination.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&a[i].nd.st ,&a[i].nd.nd);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld" ,&b[i].nd.st ,&b[i].nd.nd,&b[i].st.st);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 110 ms 64228 KB Output is correct
8 Correct 110 ms 64376 KB Output is correct
9 Correct 116 ms 64216 KB Output is correct
10 Incorrect 21 ms 8952 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2296 ms 404716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2296 ms 404716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 110 ms 64228 KB Output is correct
8 Correct 110 ms 64376 KB Output is correct
9 Correct 116 ms 64216 KB Output is correct
10 Incorrect 21 ms 8952 KB Output isn't correct
11 Halted 0 ms 0 KB -