oj.uz

Submission #66112

# Submission time Handle Problem Language Result Execution time Memory
66112 2018-08-09T15:22:10 Z FLDutchman Game (IOI13_game) C++14
10 / 100
 13000 ms 13296 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define fst first
#define snd second
#define fast_io() ios::sync_with_stdio(false)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define H(x) cout << #x << " " << x << endl;

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;
typedef double ld;
typedef pair<ld, ld> dd;

const ll INF = 1000000000000000000LL;
const int NMAX = 1e6+4;
const int mod = 1e9+7;
const ld eps = 1e-10;
const ld PI = acos(-1);

int cnt = 0;


long long gcd2(long long X, long long Y) {
    cnt++;
    //return 0;
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}


struct segtree {
    segtree *l, *r;
    long long gcd = 0;
    segtree* lc(){
        if(!l) l = new segtree();
        return l;
    }
    segtree* rc(){
        if(!r) r = new segtree();
        return r;
    }
};

int XMAX, YMAX;
segtree* t;

void upd( segtree *t, int x, int y, long long v, int xl, int xr, int yl, int yr ){
    if(xr - xl == 1 and yr - yl == 1) {
        t->gcd = v;
        return;
    }
    if(xr-xl == 1) {
        upd(t, y, x, v, yl, yr, xl, xr);
        t->gcd = gcd2(t->lc()->gcd, t->rc()->gcd);
        return;
    }
    auto l = t->lc(), r = t->rc();
    ll xm = ((ll)xl + (ll)xr)/2;
    if(x < xm) upd(l, y, x, v, yl, yr, xl, xm);
    else upd(r, y, x, v, yl, yr, xm, xr);
    t->gcd = gcd2(l->gcd, r->gcd);
}

long long query(segtree *t, int qxl, int qxr, int qyl, int qyr, int xl, int xr, int yl, int yr){
    if(qxl <= xl and xr <= qxr and qyl <= yl and yr <= qyr) return t->gcd;
    if(xr-xl == 1) {
        return query(t, qyl, qyr, qxl, qxr, yl, yr, xl, xr);
    }
    ll xm = ((ll)xl+(ll)xr)/2;
    long long gcd = 0;
    if(qxl < xm) {ll tmp = !t->l ? 0 : query(t->lc(), qyl, qyr, qxl, qxr, yl, yr, xl, xm); gcd = gcd == 0 ? tmp : gcd2(gcd, tmp);}
    if(qxr > xm) {ll tmp = !t->r ? 0 : query(t->rc(), qyl, qyr, qxl, qxr, yl, yr, xm, xr); gcd = gcd == 0 ? tmp : gcd2(gcd, tmp);}
    //cout << qxl << " " << qxr << " " << qyl << " " << qyr << " " << xl << " " << xr << " " << yl << " " << yr << " " << gcd << endl; 
    return gcd;
}

void init(int R, int C) {
    XMAX = 1<<30;
    YMAX = 1<<30;
    
    t = new segtree();
}

void update(int P, int Q, long long K) {
    upd(t, P, Q, K, 0, XMAX, 0, YMAX);
}

long long calculate(int P, int Q, int U, int V) {
    //cerr<<cnt<<endl;
    return query(t, min(P, U), max(P, U)+1, min(Q, V), max(Q, V)+1, 0, XMAX, 0, YMAX);
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 3 ms 628 KB Output is correct
9 Correct 3 ms 680 KB Output is correct
10 Correct 3 ms 684 KB Output is correct
11 Correct 4 ms 684 KB Output is correct
12 Correct 2 ms 708 KB Output is correct

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4220 KB Output is correct
2 Correct 3 ms 4220 KB Output is correct
3 Correct 4 ms 4220 KB Output is correct
4 Correct 3 ms 4220 KB Output is correct
5 Correct 2 ms 4220 KB Output is correct
6 Correct 3 ms 4220 KB Output is correct
7 Correct 2 ms 4220 KB Output is correct
8 Correct 2 ms 4220 KB Output is correct
9 Correct 4 ms 4220 KB Output is correct
10 Correct 3 ms 4220 KB Output is correct
11 Correct 3 ms 4220 KB Output is correct
12 Correct 10051 ms 13296 KB Output is correct
13 Execution timed out 13038 ms 13296 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13296 KB Output is correct
2 Correct 3 ms 13296 KB Output is correct
3 Correct 4 ms 13296 KB Output is correct
4 Correct 2 ms 13296 KB Output is correct
5 Correct 2 ms 13296 KB Output is correct
6 Correct 3 ms 13296 KB Output is correct
7 Correct 2 ms 13296 KB Output is correct
8 Correct 2 ms 13296 KB Output is correct
9 Correct 2 ms 13296 KB Output is correct
10 Correct 2 ms 13296 KB Output is correct
11 Correct 2 ms 13296 KB Output is correct
12 Execution timed out 13044 ms 13296 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13296 KB Output is correct
2 Correct 3 ms 13296 KB Output is correct
3 Correct 3 ms 13296 KB Output is correct
4 Correct 3 ms 13296 KB Output is correct
5 Correct 3 ms 13296 KB Output is correct
6 Correct 3 ms 13296 KB Output is correct
7 Correct 3 ms 13296 KB Output is correct
8 Correct 2 ms 13296 KB Output is correct
9 Correct 3 ms 13296 KB Output is correct
10 Correct 3 ms 13296 KB Output is correct
11 Correct 3 ms 13296 KB Output is correct
12 Execution timed out 13083 ms 13296 KB Time limit exceeded
13 Halted 0 ms 0 KB -