oj.uz

Submission #281810

# Submission time Handle Problem Language Result Execution time Memory
281810 2020-08-23T13:55:04 Z shayan_p Game (IOI13_game) C++14
10 / 100
 13000 ms 5020 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<pii, ll> mp;
void update(int x, int y, ll w){
    mp[{x, 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.F && p.F.F <= xx && y <= p.F.S && p.F.S <= yy)
	    ans = __gcd(ans, p.S);
    }
    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 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 256 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 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Execution timed out 13008 ms 4264 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.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 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 0 ms 256 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 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Execution timed out 13029 ms 4728 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 0 ms 256 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 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 13041 ms 5020 KB Time limit exceeded
13 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 256 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 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Execution timed out 13009 ms 4344 KB Time limit exceeded
13 Halted 0 ms 0 KB -