oj.uz

Submission #281845

# Submission time Handle Problem Language Result Execution time Memory
281845 2020-08-23T14:38:59 Z shayan_p Game (IOI13_game) C++14
80 / 100
 4668 ms 256000 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];
ll g[MAX];
int C;

inline int NEW(){
    C+= 2;
    assert(C < MAX);
    return C-1;
}
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(!L[id])
	L[id] = NEW();
    if(pos < mid){
	_put(L[id], pos, x, l, mid);
    }
    else{
	_put(L[id] ^ 1, pos, x, mid, r);
    }
    g[id] = __gcd(L[id] ? g[L[id]] : 0, L[id] ? g[L[id] ^ 1] : 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, L[id] ? _ask(L[id] ^ 1, 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 384 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 256 KB Output is correct
5 Correct 1 ms 256 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 416 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 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 627 ms 12792 KB Output is correct
5 Correct 449 ms 11864 KB Output is correct
6 Correct 515 ms 8824 KB Output is correct
7 Correct 636 ms 8696 KB Output is correct
8 Correct 384 ms 6776 KB Output is correct
9 Correct 570 ms 8952 KB Output is correct
10 Correct 515 ms 8444 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 1 ms 384 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 960 ms 13380 KB Output is correct
13 Correct 1524 ms 5860 KB Output is correct
14 Correct 345 ms 3320 KB Output is correct
15 Correct 1724 ms 8184 KB Output is correct
16 Correct 242 ms 13816 KB Output is correct
17 Correct 867 ms 10488 KB Output is correct
18 Correct 1442 ms 14772 KB Output is correct
19 Correct 1287 ms 15000 KB Output is correct
20 Correct 1273 ms 14416 KB Output is correct
21 Correct 0 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 0 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 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 613 ms 12464 KB Output is correct
13 Correct 444 ms 11768 KB Output is correct
14 Correct 591 ms 8824 KB Output is correct
15 Correct 623 ms 8608 KB Output is correct
16 Correct 409 ms 6996 KB Output is correct
17 Correct 561 ms 9016 KB Output is correct
18 Correct 534 ms 8484 KB Output is correct
19 Correct 946 ms 13444 KB Output is correct
20 Correct 1465 ms 6092 KB Output is correct
21 Correct 345 ms 3220 KB Output is correct
22 Correct 1703 ms 7820 KB Output is correct
23 Correct 239 ms 13688 KB Output is correct
24 Correct 912 ms 10488 KB Output is correct
25 Correct 1439 ms 14664 KB Output is correct
26 Correct 1234 ms 14840 KB Output is correct
27 Correct 1175 ms 14328 KB Output is correct
28 Correct 965 ms 190072 KB Output is correct
29 Correct 2141 ms 210056 KB Output is correct
30 Correct 4668 ms 150748 KB Output is correct
31 Correct 4306 ms 115640 KB Output is correct
32 Correct 674 ms 2232 KB Output is correct
33 Correct 803 ms 4216 KB Output is correct
34 Correct 618 ms 206712 KB Output is correct
35 Correct 1529 ms 105772 KB Output is correct
36 Correct 2920 ms 206872 KB Output is correct
37 Correct 2296 ms 206888 KB Output is correct
38 Correct 2220 ms 206200 KB Output is correct
39 Correct 1958 ms 159396 KB Output is correct
40 Correct 0 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 0 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 584 ms 11256 KB Output is correct
13 Correct 442 ms 11256 KB Output is correct
14 Correct 523 ms 8216 KB Output is correct
15 Correct 588 ms 7928 KB Output is correct
16 Correct 394 ms 6440 KB Output is correct
17 Correct 537 ms 8056 KB Output is correct
18 Correct 503 ms 7672 KB Output is correct
19 Correct 945 ms 12408 KB Output is correct
20 Correct 1461 ms 5072 KB Output is correct
21 Correct 333 ms 2296 KB Output is correct
22 Correct 1713 ms 7284 KB Output is correct
23 Correct 245 ms 13048 KB Output is correct
24 Correct 902 ms 9592 KB Output is correct
25 Correct 1516 ms 13732 KB Output is correct
26 Correct 1232 ms 13780 KB Output is correct
27 Correct 1132 ms 13240 KB Output is correct
28 Correct 948 ms 188920 KB Output is correct
29 Correct 2075 ms 209640 KB Output is correct
30 Correct 4660 ms 150984 KB Output is correct
31 Correct 4470 ms 116464 KB Output is correct
32 Correct 684 ms 3320 KB Output is correct
33 Correct 876 ms 5132 KB Output is correct
34 Correct 681 ms 207864 KB Output is correct
35 Correct 1731 ms 106752 KB Output is correct
36 Correct 3391 ms 207992 KB Output is correct
37 Correct 2499 ms 208200 KB Output is correct
38 Correct 2619 ms 207588 KB Output is correct
39 Runtime error 1257 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -