oj.uz

Submission #131637

# Submission time Handle Problem Language Result Execution time Memory
131637 2019-07-17T10:55:57 Z ekrem Examination (JOI19_examination) C++
20 / 100
 1795 ms 205268 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 < 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

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.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1767 ms 203980 KB Output is correct
2 Correct 1751 ms 204860 KB Output is correct
3 Correct 1749 ms 205056 KB Output is correct
4 Correct 249 ms 24824 KB Output is correct
5 Correct 268 ms 22988 KB Output is correct
6 Correct 92 ms 5112 KB Output is correct
7 Correct 1795 ms 204844 KB Output is correct
8 Correct 1685 ms 204920 KB Output is correct
9 Correct 1533 ms 204612 KB Output is correct
10 Correct 120 ms 9368 KB Output is correct
11 Correct 143 ms 9940 KB Output is correct
12 Correct 58 ms 4700 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1767 ms 203980 KB Output is correct
2 Correct 1751 ms 204860 KB Output is correct
3 Correct 1749 ms 205056 KB Output is correct
4 Correct 249 ms 24824 KB Output is correct
5 Correct 268 ms 22988 KB Output is correct
6 Correct 92 ms 5112 KB Output is correct
7 Correct 1795 ms 204844 KB Output is correct
8 Correct 1685 ms 204920 KB Output is correct
9 Correct 1533 ms 204612 KB Output is correct
10 Correct 120 ms 9368 KB Output is correct
11 Correct 143 ms 9940 KB Output is correct
12 Correct 58 ms 4700 KB Output is correct
13 Incorrect 1523 ms 205268 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

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