oj.uz

Submission #117612

# Submission time Handle Problem Language Result Execution time Memory
117612 2019-06-16T19:04:04 Z Bruteforceman Tenis (COI19_tenis) C++11
39 / 100
 128 ms 6452 KB 
#include "bits/stdc++.h"
using namespace std;
int N, Q;
int a[4][100010];
int p[4][100010];
int t[100010 * 4];
int prop[100010 * 4];

void pushdown(int c) {
	int l = c << 1;
	int r = l + 1;
	t[l] += prop[c];
	t[r] += prop[c];
	prop[l] += prop[c];
	prop[r] += prop[c];
	prop[c] = 0;
}
void upd(int x, int y, int val, int c = 1, int b = 1, int e = N) {
	if(x <= b && e <= y) {
		t[c] += val;
		prop[c] += val;
		return ;
	}
	if(y < b || e < x) return ;
	pushdown(c);
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	upd(x, y, val, l, b, m);
	upd(x, y, val, r, m + 1, e);
	t[c] = min(t[l], t[r]);
}
int query(int x, int y, int c = 1, int b = 1, int e = N) {
	if(x <= b && e <= y) {
		return t[c];
	}
	if(y < b || e < x) return N;
	pushdown(c);
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	return min(query(x, y, l, b, m), query(x, y, r, m + 1, e));
}

int add(int r, int pos, int val) {
	a[r][pos] = val;
	if(pos > 1 && a[r][pos - 1] != -1) {
		int prev = a[r][pos - 1];
		if(val < prev) {
			upd(val, prev - 1, 1);
		}
	}
	if(pos < N && a[r][pos + 1] != -1) {
		int nxt = a[r][pos + 1];
		if(nxt < val) {
			upd(nxt, val - 1, 1);
		}
	}
}
int rem(int r, int pos) {
	int val = a[r][pos];
	if(pos > 1 && a[r][pos - 1] != -1) {
		int prev = a[r][pos - 1];
		if(val < prev) {
			upd(val, prev - 1, -1);
		}
	}
	if(pos < N && a[r][pos + 1] != -1) {
		int nxt = a[r][pos + 1];
		if(nxt < val) {
			upd(nxt, val - 1, -1);
		}
	}
	a[r][pos] = -1;
}
void update(int q, int x, int y) {
	if(q == 1) {
		update(2, x, y);
		update(3, x, y);
		swap(p[1][x], p[1][y]);
	} else {
		int f = p[q][x];
		int g = p[q][y];
		int v1 = a[q][f];
		int v2 = a[q][g];
		rem(q, f);
		rem(q, g);
		add(q, f, v2);
		add(q, g, v1);
		swap(p[q][x], p[q][y]);
	}
	// cout << endl;
	// for(int i = 2; i <= 3; i++) {
	// 	for(int j = 1; j <= N; j++) {
	// 		cout << a[i][j] << ' ';
	// 	}
	// 	cout << endl;
	// }
}

int main(int argc, char const *argv[])
{
	scanf("%d %d", &N, &Q);
	for(int i = 1; i <= 3; i++) {
		for(int j = 1; j <= N; j++) {
			scanf("%d", &a[i][j]);
			p[i][a[i][j]] = j;
		}
	}
	for(int i = 2; i <= 3; i++) {
		for(int j = 1; j <= N; j++) {
			a[i][j] = p[1][a[i][j]];
			p[i][a[i][j]] = j;
			if(j > 1 && a[i][j - 1] > a[i][j]) {
				upd(a[i][j], a[i][j - 1] - 1, 1);
			}
			// cout << a[i][j] << ' ';
		}
		// cout << endl;
	}
	for(int i = 1; i <= Q; i++) {
		int c;
		scanf("%d", &c);
		if(c == 1) {
			int x;
			scanf("%d", &x);
			if(p[1][x] == 1 || query(1, p[1][x] - 1) > 0) printf("DA\n");
			else printf("NE\n");
		} else {
			int f, x, y;
			scanf("%d %d %d", &f, &x, &y);
			update(f, p[1][x], p[1][y]);
		}
	}	
	return 0;
}

Compilation message

tenis.cpp: In function 'int add(int, int, int)':
tenis.cpp:59:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
tenis.cpp: In function 'int rem(int, int)':
tenis.cpp:75:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
tenis.cpp: In function 'int main(int, const char**)':
tenis.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~
tenis.cpp:106:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~
tenis.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c);
   ~~~~~^~~~~~~~~~
tenis.cpp:126:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~
tenis.cpp:131:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &f, &x, &y);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 70 ms 5496 KB Output is correct
14 Correct 74 ms 5624 KB Output is correct
15 Correct 72 ms 5724 KB Output is correct
16 Correct 72 ms 5752 KB Output is correct
17 Correct 66 ms 5752 KB Output is correct
18 Incorrect 69 ms 5596 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 6452 KB Output is correct
2 Correct 122 ms 5880 KB Output is correct
3 Correct 126 ms 5852 KB Output is correct
4 Correct 119 ms 5880 KB Output is correct
5 Correct 122 ms 5892 KB Output is correct
6 Correct 116 ms 6044 KB Output is correct
7 Correct 128 ms 5852 KB Output is correct
8 Correct 117 ms 5972 KB Output is correct
9 Correct 123 ms 5920 KB Output is correct
10 Correct 125 ms 5880 KB Output is correct
11 Correct 119 ms 5932 KB Output is correct
12 Correct 117 ms 5880 KB Output is correct
13 Correct 127 ms 5888 KB Output is correct
14 Correct 122 ms 5880 KB Output is correct
15 Correct 120 ms 5880 KB Output is correct

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 70 ms 5496 KB Output is correct
14 Correct 74 ms 5624 KB Output is correct
15 Correct 72 ms 5724 KB Output is correct
16 Correct 72 ms 5752 KB Output is correct
17 Correct 66 ms 5752 KB Output is correct
18 Incorrect 69 ms 5596 KB Output isn't correct
19 Halted 0 ms 0 KB -