oj.uz

Submission #250329

# Submission time Handle Problem Language Result Execution time Memory
250329 2020-07-17T12:09:02 Z MarcoMeijer Game (IOI13_game) C++14
37 / 100
 787 ms 12408 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()

int R, C;

ll gcd(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct Seg {
    int bg, ed;
    ll val;
    Seg* ls=nullptr;
    Seg* rs=nullptr;

    Seg(int l, int r, ll v=0) {
        bg=l; ed=r; val=v;
    }
    ll f(Seg* s) {
        if(s == nullptr) return 0;
        return s->val;
    }
    ll f(Seg* s, int i, int j, int l, int r) {
        if(s == nullptr) return 0;
        return s->get(i,j,l,r);
    }
    void set(int i, ll v, int l, int r) {
        int m=(l+r)/2;
        if(l == r) {
            val = v;
            return;
        }
        if(i <= m) {
            if(ls == nullptr) ls = new Seg(l,m);
            ls->set(i,v,l,m);
        } else {
            if(rs == nullptr) rs = new Seg(m+1,r);
            rs->set(i,v,m+1,r);
        }
        val = gcd(f(ls), f(rs));
    }
    ll get(int i, int j, int l, int r) {
        if(j < l || i > r) return 0;
        if(i <= l && j >= r) return val;
        int m=(l+r)/2;
        ll a = f(ls,i,j,l,m);
        ll b = f(rs,i,j,m+1,r);
        return gcd(a,b);
    }
};


Seg* SEG[100];
/*
struct Seg2 {
    int bg, ed;
    Seg val;
    Seg2* ls=nullptr;
    Seg2* rs=nullptr;
    
    Seg2(int l, int r) : val(0,C-1) {
        bg = l; ed = r;
    }
    void set(int i, int j, ll v, int l, int r) {
        int m=(l+r)/2;
        val.set(j,v,0,C-1);
        if(l == r) {
            return;
        }
        if(i <= m) {
            if(ls == nullptr) ls = new Seg2(l,m);
            ls->set(i,j,v,l,m);
        } else {
            if(rs == nullptr) rs = new Seg2(m+1,r);
            rs->set(i,j,v,m+1,r);
        }
    }
    ll f(Seg2* s, int i, int j, int I, int J, int l, int r) {
        if(s == nullptr) return 0;
        return s->get(i,j,I,J,l,r);
    }
    ll get(int i, int j, int I, int J, int l, int r) {
        if(j < l || i > r) return 0;
        if(i <= l && j >= r) return val.get(I,J,0,C-1);
        int m=(l+r)/2;
        ll a = f(ls,i,j,I,J,l,m);
        ll b = f(rs,i,j,I,J,m+1,r);
        return gcd(a,b);
    }
};

Seg2* SEG;*/

void init(int _R, int _C) {
    R = _R;
    C = _C;
    //SEG = new Seg2(0,R-1);
    RE(i,R) SEG[i] = new Seg(0,C-1);
}

void update(int P, int Q, ll K) {
    //SEG->set(P,Q,K,0,R-1);
    SEG[P]->set(Q,K,0,C-1);
}

ll calculate(int P, int Q, int U, int V) {
    ll ans = 0;
    REP(i,P,U+1) ans = gcd(ans, SEG[i]->get(Q,V,0,C-1));
    return ans;
    //return SEG->get(P,U,Q,V,0,R-1);
}

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 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 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 384 KB Output is correct
11 Correct 0 ms 384 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 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 661 ms 12392 KB Output is correct
5 Correct 384 ms 12280 KB Output is correct
6 Correct 590 ms 9720 KB Output is correct
7 Correct 787 ms 9464 KB Output is correct
8 Correct 433 ms 8208 KB Output is correct
9 Correct 623 ms 9568 KB Output is correct
10 Correct 553 ms 9216 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 0 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 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 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 324 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 642 ms 12408 KB Output is correct
13 Correct 381 ms 12152 KB Output is correct
14 Correct 591 ms 9720 KB Output is correct
15 Correct 685 ms 9464 KB Output is correct
16 Correct 448 ms 8184 KB Output is correct
17 Correct 649 ms 9592 KB Output is correct
18 Correct 604 ms 9208 KB Output is correct
19 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

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 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 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 635 ms 12280 KB Output is correct
13 Correct 371 ms 12152 KB Output is correct
14 Correct 567 ms 9764 KB Output is correct
15 Correct 624 ms 9592 KB Output is correct
16 Correct 453 ms 8256 KB Output is correct
17 Correct 605 ms 9704 KB Output is correct
18 Correct 543 ms 9208 KB Output is correct
19 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -