oj.uz

Submission #281812

# Submission time Handle Problem Language Result Execution time Memory
281812 2020-08-23T13:57:48 Z shayan_p Game (IOI13_game) C++14
37 / 100
 13000 ms 8152 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;

int N, M;

struct node{
    ll g = 0;
    node *L = 0, *R = 0;
    void put(int pos, ll x, int l = 0, int r = M){
	if(r-l == 1){
	    g = x;
	    return;
	}
	int mid = (l+r) >> 1;
	if(pos < mid){
	    if(!L)
		L = new node();
	    L->put(pos, x, l, mid);
	}
	else{
	    if(!R)
		R = new node();
	    R->put(pos, x, mid, r);
	}
	g = __gcd(L ? L->g : 0, R ? R->g : 0);
    }
    ll ask(int f, int s, int l = 0, int r = M){
	if(r <= f || s <= l)
	    return 0;
	if(f <= l && r <= s)
	    return g;
	int mid = (l+r) >> 1;
	return __gcd(L ? L->ask(f, s, l, mid) : 0, R ? R->ask(f, s, mid, r) : 0);
    }
};
struct node2{
    node* g = 0;
    node2 *L = 0, *R = 0;
    void put(int posx, int posy, ll x, int l = 0, int r = N){
	if(!g)
	    g = new node();
	g->put(posy, x);
	if(r-l == 1){
	    return;
	}
	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);
	}
    }
    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 ? g->ask(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();
}

map<int, node*> mp;
void update(int x, int y, ll w){
    if(mp.count(x) == 0)
	mp[x] = new node();
    mp[x]->put(y, w);
    // root->put(x, y, w);
}
ll calculate(int x, int y, int xx, int yy){
    ll ans = 0;
    for(auto p : mp){
	if(x <= p.F && p.F <= xx)
	    ans = __gcd(ans, p.S->ask(y, yy+1));
    }
    return ans;
    //    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 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 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 256 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 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 721 ms 7544 KB Output is correct
5 Correct 470 ms 8152 KB Output is correct
6 Correct 574 ms 4856 KB Output is correct
7 Correct 647 ms 4676 KB Output is correct
8 Correct 462 ms 4472 KB Output is correct
9 Correct 610 ms 4728 KB Output is correct
10 Correct 585 ms 4344 KB Output is correct
11 Correct 1 ms 256 KB Output is correct

Subtask #3
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 256 KB Output is correct
8 Correct 1 ms 256 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 256 KB Output is correct
12 Execution timed out 13045 ms 5496 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
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 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 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 728 ms 7088 KB Output is correct
13 Correct 473 ms 7928 KB Output is correct
14 Correct 582 ms 5112 KB Output is correct
15 Correct 698 ms 4796 KB Output is correct
16 Correct 441 ms 4348 KB Output is correct
17 Correct 643 ms 4732 KB Output is correct
18 Correct 561 ms 4292 KB Output is correct
19 Execution timed out 13007 ms 6072 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.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 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 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 733 ms 6704 KB Output is correct
13 Correct 469 ms 7160 KB Output is correct
14 Correct 579 ms 3860 KB Output is correct
15 Correct 633 ms 3576 KB Output is correct
16 Correct 488 ms 3576 KB Output is correct
17 Correct 642 ms 3704 KB Output is correct
18 Correct 570 ms 3320 KB Output is correct
19 Execution timed out 13079 ms 5452 KB Time limit exceeded
20 Halted 0 ms 0 KB -