oj.uz

Submission #1092068

# Submission time Handle Problem Language Result Execution time Memory
1092068 2024-09-23T04:07:41 Z sleepntsheep Game (IOI13_game) C++17
80 / 100
 2589 ms 42652 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 22500
struct{int rt,l,r;}st[N*30];int ii,St;
struct{pos a;int b,l,r,sz;long long g,gg;}tr[N*30];int jj;
void pull(int v){if(!v)return;tr[v].sz=1+tr[tr[v].l].sz+tr[tr[v].r].sz;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
		v2=++jj;tr[v2]={{q,p},rand(),0,0,1,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 8 ms 26716 KB Output is correct
2 Correct 10 ms 26716 KB Output is correct
3 Correct 12 ms 26724 KB Output is correct
4 Correct 11 ms 26716 KB Output is correct
5 Correct 10 ms 26612 KB Output is correct
6 Correct 11 ms 26668 KB Output is correct
7 Correct 9 ms 26628 KB Output is correct
8 Correct 9 ms 26716 KB Output is correct
9 Correct 12 ms 26716 KB Output is correct
10 Correct 9 ms 26716 KB Output is correct
11 Correct 10 ms 26644 KB Output is correct
12 Correct 13 ms 26624 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26852 KB Output is correct
2 Correct 11 ms 26716 KB Output is correct
3 Correct 8 ms 26712 KB Output is correct
4 Correct 852 ms 35052 KB Output is correct
5 Correct 518 ms 35072 KB Output is correct
6 Correct 1243 ms 32464 KB Output is correct
7 Correct 1252 ms 32080 KB Output is correct
8 Correct 813 ms 32532 KB Output is correct
9 Correct 1325 ms 32340 KB Output is correct
10 Correct 1064 ms 31964 KB Output is correct
11 Correct 12 ms 26716 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26716 KB Output is correct
2 Correct 13 ms 26840 KB Output is correct
3 Correct 16 ms 26772 KB Output is correct
4 Correct 10 ms 26716 KB Output is correct
5 Correct 11 ms 26604 KB Output is correct
6 Correct 13 ms 26844 KB Output is correct
7 Correct 10 ms 26684 KB Output is correct
8 Correct 11 ms 26716 KB Output is correct
9 Correct 12 ms 26700 KB Output is correct
10 Correct 12 ms 26716 KB Output is correct
11 Correct 14 ms 26716 KB Output is correct
12 Correct 1098 ms 34868 KB Output is correct
13 Correct 1868 ms 31244 KB Output is correct
14 Correct 524 ms 31828 KB Output is correct
15 Correct 1867 ms 31960 KB Output is correct
16 Correct 585 ms 31824 KB Output is correct
17 Correct 1388 ms 32852 KB Output is correct
18 Correct 2589 ms 33108 KB Output is correct
19 Correct 2142 ms 33264 KB Output is correct
20 Correct 1845 ms 32628 KB Output is correct
21 Correct 10 ms 26712 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26716 KB Output is correct
2 Correct 11 ms 26716 KB Output is correct
3 Correct 11 ms 26728 KB Output is correct
4 Correct 9 ms 26716 KB Output is correct
5 Correct 9 ms 26716 KB Output is correct
6 Correct 11 ms 26852 KB Output is correct
7 Correct 9 ms 26716 KB Output is correct
8 Correct 10 ms 26716 KB Output is correct
9 Correct 12 ms 26816 KB Output is correct
10 Correct 10 ms 26716 KB Output is correct
11 Correct 10 ms 26712 KB Output is correct
12 Correct 781 ms 35156 KB Output is correct
13 Correct 497 ms 34896 KB Output is correct
14 Correct 1177 ms 32340 KB Output is correct
15 Correct 1299 ms 32048 KB Output is correct
16 Correct 791 ms 32592 KB Output is correct
17 Correct 1272 ms 32292 KB Output is correct
18 Correct 976 ms 31828 KB Output is correct
19 Correct 950 ms 34984 KB Output is correct
20 Correct 1740 ms 31340 KB Output is correct
21 Correct 510 ms 31824 KB Output is correct
22 Correct 1770 ms 31972 KB Output is correct
23 Correct 588 ms 31584 KB Output is correct
24 Correct 1394 ms 33032 KB Output is correct
25 Correct 2384 ms 33108 KB Output is correct
26 Correct 2128 ms 33312 KB Output is correct
27 Correct 1793 ms 32592 KB Output is correct
28 Correct 553 ms 39892 KB Output is correct
29 Correct 1140 ms 42580 KB Output is correct
30 Correct 2371 ms 35452 KB Output is correct
31 Correct 2121 ms 35412 KB Output is correct
32 Correct 513 ms 36408 KB Output is correct
33 Correct 702 ms 36436 KB Output is correct
34 Correct 786 ms 36400 KB Output is correct
35 Correct 1340 ms 38992 KB Output is correct
36 Correct 2397 ms 40276 KB Output is correct
37 Correct 1939 ms 40532 KB Output is correct
38 Correct 1724 ms 40016 KB Output is correct
39 Correct 1682 ms 39760 KB Output is correct
40 Correct 10 ms 26716 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26716 KB Output is correct
2 Correct 10 ms 26716 KB Output is correct
3 Correct 11 ms 26716 KB Output is correct
4 Correct 9 ms 26724 KB Output is correct
5 Correct 9 ms 26716 KB Output is correct
6 Correct 11 ms 26812 KB Output is correct
7 Correct 10 ms 26716 KB Output is correct
8 Correct 10 ms 26716 KB Output is correct
9 Correct 11 ms 26716 KB Output is correct
10 Correct 10 ms 26764 KB Output is correct
11 Correct 10 ms 26676 KB Output is correct
12 Correct 766 ms 35156 KB Output is correct
13 Correct 494 ms 34900 KB Output is correct
14 Correct 1157 ms 32332 KB Output is correct
15 Correct 1284 ms 32084 KB Output is correct
16 Correct 777 ms 32596 KB Output is correct
17 Correct 1265 ms 32340 KB Output is correct
18 Correct 1033 ms 31972 KB Output is correct
19 Correct 987 ms 34876 KB Output is correct
20 Correct 1850 ms 31304 KB Output is correct
21 Correct 507 ms 31824 KB Output is correct
22 Correct 1778 ms 31976 KB Output is correct
23 Correct 601 ms 31824 KB Output is correct
24 Correct 1404 ms 32848 KB Output is correct
25 Correct 2481 ms 33220 KB Output is correct
26 Correct 2170 ms 33360 KB Output is correct
27 Correct 1812 ms 32596 KB Output is correct
28 Correct 555 ms 40020 KB Output is correct
29 Correct 1181 ms 42652 KB Output is correct
30 Correct 2356 ms 35412 KB Output is correct
31 Correct 2025 ms 35156 KB Output is correct
32 Correct 495 ms 36436 KB Output is correct
33 Correct 724 ms 36432 KB Output is correct
34 Correct 777 ms 36176 KB Output is correct
35 Correct 1341 ms 38864 KB Output is correct
36 Correct 2265 ms 40528 KB Output is correct
37 Correct 1954 ms 40532 KB Output is correct
38 Correct 1745 ms 40064 KB Output is correct
39 Incorrect 723 ms 42212 KB Output isn't correct
40 Halted 0 ms 0 KB -