oj.uz

답안 #290051

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
290051 2020-09-03T10:32:47 Z egekabas 게임 (IOI13_game) C++14
37 / 100
 13000 ms 19448 KB 
#include "game.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct node{
    ll tl, tr, val;
    node *l = nullptr, *r = nullptr;
    node(ll tlval, ll trval){
        tl = tlval;
        tr = trval;
        val = 0;
    }
    node(){}
    void upd(ll idx, ll nv){
        if(tl == idx && tr == idx){
            val = nv;
            return;
        }
        ll tm = (tl+tr)/2;
        if(idx <= tm){
            if(!l)
                l = new node(tl, tm);
            l->upd(idx, nv);
        }
        else{
            if(!r)
                r = new node(tm+1, tr);
            r->upd(idx, nv);
        }
        ll xval = 0, yval = 0;
        if(l)
            xval =  l->val;
        if(r)
            yval = r->val;
        val = gcd2(xval, yval);        
    }
    ll get(ll lef, ll rig){
        
        if(tr < lef || rig < tl)
            return 0;
        if(lef <= tl && tr <= rig){
            return val;
        }
        ll xval = 0, yval = 0;
        if(l)
            xval = l->get(lef, rig);
        if(r)
            yval = r->get(lef, rig);
        return gcd2(xval, yval);
    }
};
ll r, c;
int cnt = 0;
vector<ll> v;
struct seg{
    ll tl, tr;
    node *val;
    seg *l = nullptr, *r = nullptr;
    seg(ll lval, ll rval){
        tl = lval;
        tr = rval;
        val = new node(0, c-1);
    }
    seg(){}
    void upd(ll xidx, ll yidx, ll nv){
        val->upd(yidx, nv);
        if(tl == tr){
            return;
        }
        ll tm = (tl+tr)/2;
        if(xidx <= tm){
            if(!l)
                l = new seg(tl, tm);
            l->upd(xidx, yidx, nv);
        }
        else{
            if(!r)
                r = new seg(tm+1, tr);
            r->upd(xidx, yidx, nv);
        }
    }
    void get(ll xl, ll xr, ll yl, ll yr){
        if(tr < xl || xr < tl)
            return;
        if(xl <= tl && tr <= xr){
            v.pb(val->get(yl, yr));
        }
        if(l)
            l->get(xl, xr, yl, yr);
        if(r)
            r->get(xl, xr, yl, yr);
    }
};
seg root;
void init(int R, int C) {
    r = R;
    c = C;
    root = seg(0, r-1);
}
    
void update(int P, int Q, long long K) {
    root.upd(P, Q, K);
}
    
long long calculate(int P, int Q, int U, int V){    
    v.clear();
    root.get(P, U, Q, V);
    ll ans = 0;
    for(auto u : v){
        ans = gcd2(ans, u);
    }
    return ans;
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 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 512 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 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1248 ms 19396 KB Output is correct
5 Correct 730 ms 19448 KB Output is correct
6 Correct 1040 ms 16376 KB Output is correct
7 Correct 1259 ms 16208 KB Output is correct
8 Correct 721 ms 11208 KB Output is correct
9 Correct 1203 ms 16396 KB Output is correct
10 Correct 1164 ms 15996 KB Output is correct
11 Correct 1 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 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 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 416 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Execution timed out 13059 ms 10768 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 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 512 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 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1254 ms 19284 KB Output is correct
13 Correct 730 ms 19356 KB Output is correct
14 Correct 1028 ms 16376 KB Output is correct
15 Correct 1271 ms 16120 KB Output is correct
16 Correct 698 ms 11296 KB Output is correct
17 Correct 1181 ms 16296 KB Output is correct
18 Correct 1145 ms 15736 KB Output is correct
19 Execution timed out 13054 ms 10656 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 0 ms 360 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 512 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 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1262 ms 19168 KB Output is correct
13 Correct 748 ms 19448 KB Output is correct
14 Correct 1110 ms 16456 KB Output is correct
15 Correct 1276 ms 16184 KB Output is correct
16 Correct 704 ms 11604 KB Output is correct
17 Correct 1204 ms 16376 KB Output is correct
18 Correct 1116 ms 15992 KB Output is correct
19 Execution timed out 13095 ms 10844 KB Time limit exceeded
20 Halted 0 ms 0 KB -