oj.uz

Submission #127638

# Submission time Handle Problem Language Result Execution time Memory
127638 2019-07-09T19:07:14 Z hamzqq9 Game (IOI13_game) C++14
100 / 100
 12584 ms 39416 KB 
#include "game.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define inf 1000000000
#define MOD 1000000007 
#define N 10000005
#define M 1000000
#define LOG 20
#define KOK 300
#define EPS 0.0000001
using namespace std;

struct treap {

	int key,pri;
	int l,r;
	ll val,g;

} T[N];

int root;
int go[N],l[N],r[N];
int tot_T,tot_S;

long long gcd2(long long X, long long Y) {
	if(X<Y) swap(X,Y);
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

void make2(int& node,int pos,ll val) {

	if(!node) {
	
		node=++tot_T;
		T[node].key=pos;
		T[node].pri=rand();
		T[node].l=T[node].r=0;

	}

	T[node].g=T[node].val=val;

}

void make1(int& node) {

	if(!node) node=++tot_S;

}

void relax(int root) {

	T[root].g=gcd2(gcd2(T[T[root].l].g,T[T[root].r].g),T[root].val);

}

void merge(int& root,int l,int r) {

	if(!l || !r) root=(l?l:r);
	else if(T[l].pri>T[r].pri) {

		merge(T[l].r,T[l].r,r);
		root=l;

	}
	else {

		merge(T[r].l,l,T[r].l);
		root=r;

	}

	if(root) relax(root);

}

void split(int root,int to,int& l,int& r) {

	if(!root) l=r=0;
	else if(T[root].key<=to) {

		split(T[root].r,to,T[root].r,r);
		l=root;

	}
	else {

		split(T[root].l,to,l,T[root].l);
		r=root;

	}

	if(root) relax(root);

}

ll get2(int& root,int l,int r) {

	int r1,r2,r3;

	split(root,r,r1,r3);
	split(r1,l-1,r1,r2);

	ll res=T[r2].g;

	merge(root,r1,r2);
	merge(root,root,r3);

	return res;

}

ll get1(int& node,int bas,int son,int a,int b,int c,int d) {

	if(!node) return 0;

	if(bas>=a && son<=c) return get2(go[node],b,d);

	if(orta>=a && orta+1<=c) return gcd2(get1(l[node],bas,orta,a,b,c,d),get1(r[node],orta+1,son,a,b,c,d));

	if(orta>=a) return get1(l[node],bas,orta,a,b,c,d);

	return get1(r[node],orta+1,son,a,b,c,d);

}

void up2(int& root,int pos,ll val) {

	int r1,r2,r3;

	split(root,pos,r1,r3);
	split(r1,pos-1,r1,r2);

	make2(r2,pos,val);

	merge(root,r1,r2);
	merge(root,root,r3);

}

void up1(int& node,int bas,int son,int x,int y,ll val) {

	make1(node);

	if(bas==x && son==x) {

		up2(go[node],y,val);

		return ;

	}

	if(orta>=x) up1(l[node],bas,orta,x,y,val);
	else up1(r[node],orta+1,son,x,y,val);

	ll g=gcd2(get2(go[l[node]],y,y),get2(go[r[node]],y,y));

	up2(go[node],y,g);

}

void init(int R, int C) {

	T[0].g=T[0].val=T[0].l=T[0].r=0;

	srand(time(NULL));

}

void update(int P, int Q, long long K) {

	up1(root,0,inf-1,P,Q,K);

}

long long calculate(int P, int Q, int U, int V) {

	return get1(root,0,inf-1,P,Q,U,V);

}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2245 ms 16232 KB Output is correct
5 Correct 1443 ms 16504 KB Output is correct
6 Correct 4555 ms 13380 KB Output is correct
7 Correct 4785 ms 12976 KB Output is correct
8 Correct 2809 ms 9080 KB Output is correct
9 Correct 4940 ms 13176 KB Output is correct
10 Correct 4000 ms 12680 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 13 ms 376 KB Output is correct
3 Correct 12 ms 440 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 12 ms 428 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 10 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 2443 ms 11900 KB Output is correct
13 Correct 6506 ms 7140 KB Output is correct
14 Correct 1182 ms 5732 KB Output is correct
15 Correct 6614 ms 8536 KB Output is correct
16 Correct 2237 ms 9744 KB Output is correct
17 Correct 4666 ms 9380 KB Output is correct
18 Correct 8130 ms 11168 KB Output is correct
19 Correct 7345 ms 11288 KB Output is correct
20 Correct 6580 ms 10716 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 13 ms 472 KB Output is correct
3 Correct 12 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 12 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 10 ms 504 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 2310 ms 16120 KB Output is correct
13 Correct 1472 ms 16588 KB Output is correct
14 Correct 4490 ms 13176 KB Output is correct
15 Correct 4796 ms 12980 KB Output is correct
16 Correct 2733 ms 9080 KB Output is correct
17 Correct 4820 ms 13136 KB Output is correct
18 Correct 4009 ms 12832 KB Output is correct
19 Correct 2464 ms 11764 KB Output is correct
20 Correct 6411 ms 7288 KB Output is correct
21 Correct 1162 ms 5752 KB Output is correct
22 Correct 6787 ms 8472 KB Output is correct
23 Correct 1755 ms 9716 KB Output is correct
24 Correct 4618 ms 9384 KB Output is correct
25 Correct 8082 ms 11184 KB Output is correct
26 Correct 7167 ms 11320 KB Output is correct
27 Correct 6652 ms 10660 KB Output is correct
28 Correct 2343 ms 23368 KB Output is correct
29 Correct 2927 ms 25976 KB Output is correct
30 Correct 8422 ms 17840 KB Output is correct
31 Correct 7245 ms 15680 KB Output is correct
32 Correct 1143 ms 10360 KB Output is correct
33 Correct 1770 ms 10488 KB Output is correct
34 Correct 1462 ms 19704 KB Output is correct
35 Correct 4567 ms 17628 KB Output is correct
36 Correct 8144 ms 24028 KB Output is correct
37 Correct 6961 ms 24160 KB Output is correct
38 Correct 7285 ms 23600 KB Output is correct
39 Correct 5875 ms 21028 KB Output is correct
40 Correct 2 ms 376 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 13 ms 376 KB Output is correct
3 Correct 12 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 12 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 10 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 2296 ms 16724 KB Output is correct
13 Correct 1440 ms 16876 KB Output is correct
14 Correct 4582 ms 13708 KB Output is correct
15 Correct 4810 ms 13272 KB Output is correct
16 Correct 2699 ms 9472 KB Output is correct
17 Correct 4872 ms 13428 KB Output is correct
18 Correct 4001 ms 13236 KB Output is correct
19 Correct 2408 ms 11740 KB Output is correct
20 Correct 6279 ms 7248 KB Output is correct
21 Correct 1186 ms 5880 KB Output is correct
22 Correct 6920 ms 8624 KB Output is correct
23 Correct 1580 ms 9720 KB Output is correct
24 Correct 4774 ms 9464 KB Output is correct
25 Correct 8172 ms 11060 KB Output is correct
26 Correct 7361 ms 11152 KB Output is correct
27 Correct 6620 ms 10852 KB Output is correct
28 Correct 2352 ms 23416 KB Output is correct
29 Correct 2998 ms 26012 KB Output is correct
30 Correct 8568 ms 17932 KB Output is correct
31 Correct 7162 ms 15540 KB Output is correct
32 Correct 1124 ms 10232 KB Output is correct
33 Correct 1792 ms 10460 KB Output is correct
34 Correct 1315 ms 19736 KB Output is correct
35 Correct 4573 ms 17608 KB Output is correct
36 Correct 8128 ms 23968 KB Output is correct
37 Correct 6762 ms 24064 KB Output is correct
38 Correct 7239 ms 23416 KB Output is correct
39 Correct 3349 ms 37176 KB Output is correct
40 Correct 4933 ms 39416 KB Output is correct
41 Correct 12584 ms 29760 KB Output is correct
42 Correct 11481 ms 24336 KB Output is correct
43 Correct 2551 ms 34064 KB Output is correct
44 Correct 1850 ms 10644 KB Output is correct
45 Correct 5753 ms 21020 KB Output is correct
46 Correct 10863 ms 38176 KB Output is correct
47 Correct 10893 ms 38268 KB Output is correct
48 Correct 10847 ms 37816 KB Output is correct
49 Correct 2 ms 380 KB Output is correct