oj.uz

Submission #281851

# Submission time Handle Problem Language Result Execution time Memory
281851 2020-08-23T14:43:41 Z shayan_p Game (IOI13_game) C++14
80 / 100
 4533 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 = 175e5;

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 0 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 0 ms 256 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 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 596 ms 9956 KB Output is correct
5 Correct 471 ms 12152 KB Output is correct
6 Correct 501 ms 8988 KB Output is correct
7 Correct 591 ms 8664 KB Output is correct
8 Correct 388 ms 7288 KB Output is correct
9 Correct 568 ms 8952 KB Output is correct
10 Correct 508 ms 8568 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 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 256 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 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 925 ms 11640 KB Output is correct
13 Correct 1758 ms 6356 KB Output is correct
14 Correct 350 ms 3576 KB Output is correct
15 Correct 1957 ms 8192 KB Output is correct
16 Correct 279 ms 14456 KB Output is correct
17 Correct 916 ms 10672 KB Output is correct
18 Correct 1720 ms 15172 KB Output is correct
19 Correct 1196 ms 15480 KB Output is correct
20 Correct 1189 ms 14804 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 0 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 0 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 585 ms 9956 KB Output is correct
13 Correct 442 ms 12152 KB Output is correct
14 Correct 532 ms 8992 KB Output is correct
15 Correct 577 ms 8772 KB Output is correct
16 Correct 430 ms 7416 KB Output is correct
17 Correct 549 ms 8824 KB Output is correct
18 Correct 553 ms 8444 KB Output is correct
19 Correct 927 ms 13688 KB Output is correct
20 Correct 1451 ms 6596 KB Output is correct
21 Correct 333 ms 3832 KB Output is correct
22 Correct 1706 ms 8724 KB Output is correct
23 Correct 240 ms 14712 KB Output is correct
24 Correct 869 ms 10872 KB Output is correct
25 Correct 1466 ms 15568 KB Output is correct
26 Correct 1236 ms 15732 KB Output is correct
27 Correct 1140 ms 14324 KB Output is correct
28 Correct 977 ms 190200 KB Output is correct
29 Correct 2205 ms 210640 KB Output is correct
30 Correct 4533 ms 151544 KB Output is correct
31 Correct 4380 ms 116628 KB Output is correct
32 Correct 666 ms 3320 KB Output is correct
33 Correct 848 ms 5112 KB Output is correct
34 Correct 624 ms 207888 KB Output is correct
35 Correct 1501 ms 106876 KB Output is correct
36 Correct 2781 ms 208068 KB Output is correct
37 Correct 2348 ms 208368 KB Output is correct
38 Correct 2325 ms 207636 KB Output is correct
39 Correct 1955 ms 160632 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 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 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 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 603 ms 10104 KB Output is correct
13 Correct 440 ms 12408 KB Output is correct
14 Correct 523 ms 9768 KB Output is correct
15 Correct 571 ms 9596 KB Output is correct
16 Correct 392 ms 7800 KB Output is correct
17 Correct 568 ms 9584 KB Output is correct
18 Correct 576 ms 9184 KB Output is correct
19 Correct 931 ms 14456 KB Output is correct
20 Correct 1453 ms 6960 KB Output is correct
21 Correct 338 ms 4124 KB Output is correct
22 Correct 1719 ms 8656 KB Output is correct
23 Correct 237 ms 14840 KB Output is correct
24 Correct 828 ms 11544 KB Output is correct
25 Correct 1391 ms 15904 KB Output is correct
26 Correct 1187 ms 15992 KB Output is correct
27 Correct 1232 ms 15536 KB Output is correct
28 Correct 992 ms 190840 KB Output is correct
29 Correct 2099 ms 210424 KB Output is correct
30 Correct 4474 ms 150136 KB Output is correct
31 Correct 4352 ms 114480 KB Output is correct
32 Correct 670 ms 1144 KB Output is correct
33 Correct 824 ms 3064 KB Output is correct
34 Correct 681 ms 205800 KB Output is correct
35 Correct 1544 ms 104556 KB Output is correct
36 Correct 2732 ms 205948 KB Output is correct
37 Correct 2335 ms 206028 KB Output is correct
38 Correct 2398 ms 205708 KB Output is correct
39 Runtime error 962 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -