oj.uz

Submission #1092072

# Submission time Handle Problem Language Result Execution time Memory
1092072 2024-09-23T04:11:15 Z sleepntsheep Game (IOI13_game) C++17
100 / 100
 3905 ms 252740 KB 
#include "game.h"
#include <stdlib.h>
#include <stdio.h>
#include <utility>
long long gcd2(long long X, long long Y) { return Y ? gcd2(Y, X % Y) : X; }
using pos=std::pair<int,int>;
#define N 200000
struct{int rt,l,r;}st[N*30];int ii,St;
struct{pos a;int b,l,r;long long g,gg;}tr[N*30];int jj;
void pull(int v){tr[v].gg=gcd2(tr[v].g,gcd2(tr[tr[v].l].gg,tr[tr[v].r].gg));}
void merge(int&v,int l,int r){
	if(!l||!r)return void(v=l^r);
	if(tr[l].b<tr[r].b) merge(tr[r].l,l,tr[r].l),v=r;
	else merge(tr[l].r,tr[l].r,r),v=l;
	pull(v);
}
void split(int v,int&l,int&r,pos p){
	if(!v)return void(l=r=0);
	if(tr[v].a<=p)split(tr[v].r,tr[v].r,r,p),l=v;
	else split(tr[v].l,l,tr[v].l,p),r=v;
	pull(v);
}

void upd(int&v,int l,int r,int p,int q,long long k){
	if(!v)v=++ii;
	{
		int v1,v2,v3;
		split(st[v].rt,v1,v2,{q,p-1});
		split(v2,v2,v3,{q,p});
		if(v2)tr[v2].g=tr[v2].gg=k;
		else tr[v2=++jj]={{q,p},rand(),0,0,k,k};
		merge(v1,v1,v2);
		merge(st[v].rt,v1,v3);
	}
	if(l==r)return;
	if(p<=(l+r)/2)upd(st[v].l,l,(l+r)/2,p,q,k);
	else upd(st[v].r,(l+r)/2+1,r,p,q,k);
}

long long qry(int v,int l,int r,int x,int y,int w,int z){
	if(!v||r<x||y<l)return 0;
	if(x<=l&&r<=y){
		int v1,v2,v3;long long zz;
		split(st[v].rt,v1,v2,{w-1,2e9});
		split(v2,v2,v3,{z,2e9});
		zz=tr[v2].gg;
		merge(v2,v2,v3);
		merge(st[v].rt,v1,v2);
		return zz;
	}
	return gcd2(qry(st[v].l,l,(l+r)/2,x,y,w,z),qry(st[v].r,(l+r)/2+1,r,x,y,w,z));
}

void init(int R, int C) { }
void update(int P, int Q, long long K) { upd(St,0,1e9,P,Q,K); }
long long calculate(int P, int Q, int U, int V) { return qry(St,0,1e9,P,U,Q,V); }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 235092 KB Output is correct
2 Correct 86 ms 235088 KB Output is correct
3 Correct 87 ms 235032 KB Output is correct
4 Correct 83 ms 235012 KB Output is correct
5 Correct 83 ms 235092 KB Output is correct
6 Correct 112 ms 235088 KB Output is correct
7 Correct 83 ms 235228 KB Output is correct
8 Correct 86 ms 235152 KB Output is correct
9 Correct 81 ms 235088 KB Output is correct
10 Correct 79 ms 235088 KB Output is correct
11 Correct 80 ms 235120 KB Output is correct
12 Correct 78 ms 235140 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 235092 KB Output is correct
2 Correct 87 ms 235116 KB Output is correct
3 Correct 85 ms 235084 KB Output is correct
4 Correct 872 ms 243460 KB Output is correct
5 Correct 529 ms 243280 KB Output is correct
6 Correct 1209 ms 240720 KB Output is correct
7 Correct 1346 ms 240724 KB Output is correct
8 Correct 842 ms 240980 KB Output is correct
9 Correct 1320 ms 240720 KB Output is correct
10 Correct 1038 ms 240180 KB Output is correct
11 Correct 79 ms 235064 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 235088 KB Output is correct
2 Correct 80 ms 235044 KB Output is correct
3 Correct 86 ms 235088 KB Output is correct
4 Correct 88 ms 235088 KB Output is correct
5 Correct 82 ms 235140 KB Output is correct
6 Correct 85 ms 235092 KB Output is correct
7 Correct 83 ms 235088 KB Output is correct
8 Correct 83 ms 235088 KB Output is correct
9 Correct 81 ms 235092 KB Output is correct
10 Correct 79 ms 235164 KB Output is correct
11 Correct 79 ms 235028 KB Output is correct
12 Correct 1014 ms 243280 KB Output is correct
13 Correct 1748 ms 239700 KB Output is correct
14 Correct 564 ms 240464 KB Output is correct
15 Correct 1800 ms 240256 KB Output is correct
16 Correct 636 ms 240056 KB Output is correct
17 Correct 1456 ms 241236 KB Output is correct
18 Correct 2620 ms 241596 KB Output is correct
19 Correct 2206 ms 241640 KB Output is correct
20 Correct 1845 ms 241136 KB Output is correct
21 Correct 87 ms 235092 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 235088 KB Output is correct
2 Correct 82 ms 235084 KB Output is correct
3 Correct 87 ms 235088 KB Output is correct
4 Correct 81 ms 235088 KB Output is correct
5 Correct 83 ms 235012 KB Output is correct
6 Correct 81 ms 235096 KB Output is correct
7 Correct 79 ms 235064 KB Output is correct
8 Correct 79 ms 235092 KB Output is correct
9 Correct 82 ms 235092 KB Output is correct
10 Correct 86 ms 235036 KB Output is correct
11 Correct 82 ms 234992 KB Output is correct
12 Correct 826 ms 243536 KB Output is correct
13 Correct 539 ms 243284 KB Output is correct
14 Correct 1223 ms 240724 KB Output is correct
15 Correct 1337 ms 240464 KB Output is correct
16 Correct 848 ms 240976 KB Output is correct
17 Correct 1305 ms 240720 KB Output is correct
18 Correct 1043 ms 240332 KB Output is correct
19 Correct 967 ms 243284 KB Output is correct
20 Correct 1848 ms 239724 KB Output is correct
21 Correct 559 ms 240464 KB Output is correct
22 Correct 1878 ms 240404 KB Output is correct
23 Correct 654 ms 240208 KB Output is correct
24 Correct 1490 ms 241408 KB Output is correct
25 Correct 2545 ms 241588 KB Output is correct
26 Correct 2175 ms 241728 KB Output is correct
27 Correct 1817 ms 240976 KB Output is correct
28 Correct 608 ms 248404 KB Output is correct
29 Correct 1207 ms 250960 KB Output is correct
30 Correct 2347 ms 243832 KB Output is correct
31 Correct 2119 ms 243756 KB Output is correct
32 Correct 565 ms 244788 KB Output is correct
33 Correct 778 ms 244896 KB Output is correct
34 Correct 865 ms 244764 KB Output is correct
35 Correct 1410 ms 247284 KB Output is correct
36 Correct 2452 ms 248856 KB Output is correct
37 Correct 2001 ms 248884 KB Output is correct
38 Correct 1786 ms 248408 KB Output is correct
39 Correct 1712 ms 248196 KB Output is correct
40 Correct 86 ms 235132 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 234996 KB Output is correct
2 Correct 85 ms 235020 KB Output is correct
3 Correct 86 ms 235096 KB Output is correct
4 Correct 88 ms 235092 KB Output is correct
5 Correct 83 ms 235072 KB Output is correct
6 Correct 86 ms 235000 KB Output is correct
7 Correct 81 ms 235096 KB Output is correct
8 Correct 89 ms 235088 KB Output is correct
9 Correct 92 ms 235092 KB Output is correct
10 Correct 83 ms 235180 KB Output is correct
11 Correct 85 ms 235092 KB Output is correct
12 Correct 842 ms 243664 KB Output is correct
13 Correct 540 ms 243364 KB Output is correct
14 Correct 1236 ms 240960 KB Output is correct
15 Correct 1345 ms 240656 KB Output is correct
16 Correct 853 ms 240904 KB Output is correct
17 Correct 1332 ms 240604 KB Output is correct
18 Correct 1055 ms 240264 KB Output is correct
19 Correct 986 ms 243352 KB Output is correct
20 Correct 1769 ms 239700 KB Output is correct
21 Correct 561 ms 240464 KB Output is correct
22 Correct 1850 ms 240248 KB Output is correct
23 Correct 684 ms 240208 KB Output is correct
24 Correct 1469 ms 241236 KB Output is correct
25 Correct 2581 ms 241408 KB Output is correct
26 Correct 2214 ms 241712 KB Output is correct
27 Correct 1852 ms 240976 KB Output is correct
28 Correct 631 ms 248328 KB Output is correct
29 Correct 1182 ms 250868 KB Output is correct
30 Correct 2386 ms 243788 KB Output is correct
31 Correct 2089 ms 243348 KB Output is correct
32 Correct 597 ms 244052 KB Output is correct
33 Correct 761 ms 244052 KB Output is correct
34 Correct 849 ms 244308 KB Output is correct
35 Correct 1433 ms 246360 KB Output is correct
36 Correct 2407 ms 247892 KB Output is correct
37 Correct 1977 ms 248404 KB Output is correct
38 Correct 1810 ms 248404 KB Output is correct
39 Correct 848 ms 250452 KB Output is correct
40 Correct 2051 ms 252740 KB Output is correct
41 Correct 3905 ms 245332 KB Output is correct
42 Correct 3305 ms 244820 KB Output is correct
43 Correct 945 ms 247376 KB Output is correct
44 Correct 936 ms 245076 KB Output is correct
45 Correct 1726 ms 248148 KB Output is correct
46 Correct 2878 ms 251452 KB Output is correct
47 Correct 2930 ms 251476 KB Output is correct
48 Correct 2534 ms 251000 KB Output is correct
49 Correct 94 ms 235088 KB Output is correct