Submission #117626

#	Time	Username	Problem	Language	Result	Execution time	Memory
117626		Bruteforceman	Tenis (COI19_tenis)	C++11	100 / 100	276 ms	7908 KiB

tenis

#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][a[1][x]], p[1][a[1][y]]);
		swap(a[1][x], a[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]);
	}
}
 
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);
			}
		}
	}
	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 (stderr)

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:97: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:100: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:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c);
   ~~~~~^~~~~~~~~~
tenis.cpp:118:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~
tenis.cpp:123: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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 49 / 49