oj.uz

Submission #281840

# Submission time Handle Problem Language Result Execution time Memory
281840 2020-08-23T14:31:00 Z shayan_p Game (IOI13_game) C++14
80 / 100
 4119 ms 256004 KB 
// And you curse yourself for things you never done
 
#include<bits/stdc++.h>
#include "game.h"
 
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;

const int MAX = (3e5) * 70;

int N, M;

int L[MAX], R[MAX];
ll g[MAX];
int C;

inline int NEW(){
    return ++C;
}
void _put(int id, int pos, ll x, int l = 0, int r = M){
    if(r-l == 1){
	g[id] = x;
	return;
    }
    int mid = (l+r) >> 1;
    if(pos < mid){
	if(!L[id])
	    L[id] = NEW();
	_put(L[id], pos, x, l, mid);
    }
    else{
	if(!R[id])
	    R[id] = NEW();
	_put(R[id], pos, x, mid, r);
    }
    g[id] = __gcd(L[id] ? g[L[id]] : 0, R[id] ? g[R[id]] : 0);
}
ll _ask(int id, int f, int s, int l = 0, int r = M){
    if(r <= f || s <= l)
	return 0;
    if(f <= l && r <= s)
	return g[id];
    int mid = (l+r) >> 1;
    return __gcd(L[id] ? _ask(L[id], f, s, l, mid) : 0, R[id] ? _ask(R[id], f, s, mid, r) : 0);
}
struct node2{
    int g = 0;
    node2 *L = 0, *R = 0;
    void put(int posx, int posy, ll x, int l = 0, int r = N){
	ll num = x;
	if(r-l > 1){
	    int mid = (l+r) >> 1;
	    if(posx < mid){
		if(!L)
		    L = new node2();
		L->put(posx, posy, x, l, mid);
	    }
	    else{
		if(!R)
		    R = new node2();
		R->put(posx, posy, x, mid, r);
	    }
	    num = __gcd(L ? _ask(L->g, posy, posy+1) : 0, R ? _ask(R->g, posy, posy+1) : 0);
	}
	if(!g)
	    g = NEW();
	_put(g, posy, num);
    }
    ll ask(int f, int s, int ff, int ss, int l = 0, int r = N){
	if(r <= f || s <= l)
	    return 0;
	if(f <= l && r <= s)
	    return g ? _ask(g, ff, ss) : 0;
	int mid = (l+r) >> 1;
	return __gcd(L ? L->ask(f, s, ff, ss, l, mid) : 0, R ? R->ask(f, s, ff, ss, mid, r) : 0);
    }
};
 
node2* root;
 
void init(int N, int M){
    ::N = N, ::M = M;
    root = new node2();
}
void update(int x, int y, ll w){
    root->put(x, y, w);
}
ll calculate(int x, int y, int xx, int yy){
    return root->ask(x, ++xx, y, ++yy);
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 620 ms 8520 KB Output is correct
5 Correct 463 ms 10744 KB Output is correct
6 Correct 512 ms 7672 KB Output is correct
7 Correct 652 ms 7416 KB Output is correct
8 Correct 392 ms 6264 KB Output is correct
9 Correct 542 ms 7416 KB Output is correct
10 Correct 519 ms 7032 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1010 ms 10488 KB Output is correct
13 Correct 1558 ms 4600 KB Output is correct
14 Correct 306 ms 1912 KB Output is correct
15 Correct 1816 ms 6320 KB Output is correct
16 Correct 249 ms 10872 KB Output is correct
17 Correct 862 ms 7544 KB Output is correct
18 Correct 1559 ms 11384 KB Output is correct
19 Correct 1272 ms 11128 KB Output is correct
20 Correct 1180 ms 10508 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 600 ms 8760 KB Output is correct
13 Correct 464 ms 11000 KB Output is correct
14 Correct 506 ms 7920 KB Output is correct
15 Correct 577 ms 7416 KB Output is correct
16 Correct 391 ms 6264 KB Output is correct
17 Correct 564 ms 7500 KB Output is correct
18 Correct 540 ms 7032 KB Output is correct
19 Correct 1032 ms 11896 KB Output is correct
20 Correct 1587 ms 4792 KB Output is correct
21 Correct 311 ms 2296 KB Output is correct
22 Correct 1799 ms 6776 KB Output is correct
23 Correct 246 ms 11128 KB Output is correct
24 Correct 833 ms 8312 KB Output is correct
25 Correct 1500 ms 11876 KB Output is correct
26 Correct 1375 ms 12004 KB Output is correct
27 Correct 1304 ms 11716 KB Output is correct
28 Correct 833 ms 130808 KB Output is correct
29 Correct 2222 ms 148508 KB Output is correct
30 Correct 4119 ms 108336 KB Output is correct
31 Correct 3882 ms 83848 KB Output is correct
32 Correct 547 ms 5476 KB Output is correct
33 Correct 757 ms 6832 KB Output is correct
34 Correct 566 ms 145912 KB Output is correct
35 Correct 1863 ms 76432 KB Output is correct
36 Correct 3348 ms 145784 KB Output is correct
37 Correct 2709 ms 146104 KB Output is correct
38 Correct 2647 ms 145488 KB Output is correct
39 Correct 2278 ms 113556 KB Output is correct
40 Correct 1 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 607 ms 8952 KB Output is correct
13 Correct 453 ms 10360 KB Output is correct
14 Correct 534 ms 7460 KB Output is correct
15 Correct 593 ms 7180 KB Output is correct
16 Correct 395 ms 6076 KB Output is correct
17 Correct 585 ms 7288 KB Output is correct
18 Correct 571 ms 6904 KB Output is correct
19 Correct 1018 ms 11768 KB Output is correct
20 Correct 1555 ms 5168 KB Output is correct
21 Correct 310 ms 2404 KB Output is correct
22 Correct 1856 ms 6344 KB Output is correct
23 Correct 243 ms 11260 KB Output is correct
24 Correct 849 ms 8264 KB Output is correct
25 Correct 1561 ms 11640 KB Output is correct
26 Correct 1243 ms 11888 KB Output is correct
27 Correct 1220 ms 11056 KB Output is correct
28 Correct 919 ms 130424 KB Output is correct
29 Correct 2226 ms 148356 KB Output is correct
30 Correct 4069 ms 108032 KB Output is correct
31 Correct 3794 ms 83592 KB Output is correct
32 Correct 532 ms 4600 KB Output is correct
33 Correct 722 ms 5368 KB Output is correct
34 Correct 560 ms 144632 KB Output is correct
35 Correct 1602 ms 75468 KB Output is correct
36 Correct 3005 ms 144760 KB Output is correct
37 Correct 2571 ms 145068 KB Output is correct
38 Correct 2748 ms 144484 KB Output is correct
39 Runtime error 1154 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -