Submission #385600

#	Time	Username	Problem	Language	Result	Execution time	Memory
385600		patrikpavic2	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1253 ms	78188 KiB

treearray

#include <cstdio>
#include <cstring>
#include <vector>
#include <set>

#define PB push_back

using namespace std;

const int N = 2e5 + 500;
const int LOG = 18;

int par[N][LOG], n, m, q;
int A[N], B[N], dep[N];
set < int > gdje[N], sam[N];
vector < int > v[N];

void precompute(){
	for(int j = 1;j < LOG;j++)
		for(int i = 1;i <= n;i++)
			par[i][j] = par[par[i][j - 1]][j - 1];
}

void dfs(int x, int lst){
	par[x][0] = lst;
	dep[x] = dep[lst] + 1;
	for(int y : v[x])
		if(y != lst) 
			dfs(y, x);
}

int lca(int x, int y){
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = LOG - 1;i >= 0;i--)
		if(dep[x] - (1 << i) >= dep[y])
			x = par[x][i];
	if(x == y) return x;
	for(int i = LOG - 1;i >= 0;i--)
		if(par[x][i] != par[y][i])
			x = par[x][i],
			y = par[y][i];
	return par[x][0];
}

void update(int i){
	if(i < 1 || i >= m) return;
	if(B[i]) gdje[B[i]].erase(i);
	B[i] = lca(A[i], A[i + 1]);
	gdje[B[i]].insert(i);
}

int main(){
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1;i < n;i++){
		int x, y; scanf("%d%d", &x, &y);
		v[x].PB(y), v[y].PB(x);
	}
	dfs(1, 1); precompute();
	for(int i = 1;i <= m;i++){
		scanf("%d", A + i);
		sam[A[i]].insert(i);
	}
	for(int i = 1;i < m;i++) 
		update(i);
	for(int i = 0;i < q;i++){
		int ty; scanf("%d", &ty);
		if(ty == 1){
			int x, pos; scanf("%d%d", &pos, &x);
			sam[A[pos]].erase(pos);
			A[pos] = x; update(pos); update(pos - 1);
			sam[A[pos]].insert(pos);
		}
		else{
			int l, r, x; scanf("%d%d%d", &l, &r, &x);
			if(sam[x].lower_bound(l) != sam[x].end() && *sam[x].lower_bound(l) <= r){
				int tmp = *sam[x].lower_bound(l);
				printf("%d %d\n", tmp, tmp);
			}
			else if(gdje[x].lower_bound(l) != gdje[x].end() && *gdje[x].lower_bound(l) < r){
				int tmp = *gdje[x].lower_bound(l);
				printf("%d %d\n", tmp, tmp + 1);
			}
			else{
				printf("-1 -1\n");
			}
		}
	}
	return 0;
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~
treearray.cpp:66:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |   int ty; scanf("%d", &ty);
      |           ~~~~~^~~~~~~~~~~
treearray.cpp:68:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |    int x, pos; scanf("%d%d", &pos, &x);
      |                ~~~~~^~~~~~~~~~~~~~~~~~
treearray.cpp:74:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |    int l, r, x; scanf("%d%d%d", &l, &r, &x);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44