oj.uz

Submission #99097

# Submission time Handle Problem Language Result Execution time Memory
99097 2019-02-28T14:51:30 Z figter001 Game (IOI13_game) C++14
37 / 100
 13000 ms 131188 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 1e5+50;
const ll oo = 1e18;
const ll mod = 1e9+7;

ll seg2[11][4*N];
int c,type,ro,up,dw;

struct node{
    ll sub[4500];
}seg[4500];

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;
}

ll l,r,val,cur,in;

void update2(int n,int s,int e){
    if(s > cur || e < cur)return;
    if(s == e){
        seg[in].sub[n] = val;
        return;
    }
    update2(n*2,s,(s+e)/2);
    update2(n*2+1,(s+e)/2+1,e);
    seg[in].sub[n] = gcd2(seg[in].sub[n*2],seg[in].sub[n*2+1]);
}

void merge(int n,int s,int e){
    if(s == e){
        seg[in].sub[n] = gcd2(seg[in*2].sub[n],seg[in*2+1].sub[n]);
        return;
    }
    merge(n*2,s,(s+e)/2);
    merge(n*2+1,(s+e)/2+1,e);
    seg[in].sub[n] = gcd2(seg[in].sub[n*2],seg[in].sub[n*2+1]);
}

void update1(int n,int s,int e){
    if(s > r || e < l)return;
    if(s == e){
        if(type){
            in = n;
            update2(1,1,ro);
        }else seg2[cur][n] = val;
        return;
    }
    update1(n*2,s,(s+e)/2);
    update1(n*2+1,(s+e)/2+1,e);
    if(type){
        in = n;
        merge(1,1,ro);
    }else seg2[cur][n] = gcd2(seg2[cur][n*2],seg2[cur][n*2+1]);
}

int l1,r1;
ll get1(int n,int s,int e){
    if(s > r1 || e < l1)return 0;
    if(s >= l1 && e <= r1)return seg[in].sub[n];
    return gcd2(get1(n*2,s,(s+e)/2),get1(n*2+1,(s+e)/2+1,e));
}

ll get(int n,int s,int e){
    if(s > r || e < l)return 0;
    if(s >= l && e <= r){
        if(type){
            in = n;
            l1 = up;
            r1 = dw;
            //cout << in << ' ' << up << ' ' << dw << endl;
            return get1(1,1,ro);
        }
        else return seg2[cur][n];
    }
    return gcd2(get(n*2,s,(s+e)/2),get(n*2+1,(s+e)/2+1,e));
}

void init(int R, int C) {
    type = R>10;
    c=C;
    ro=R;
}

void update(int P, int Q, long long K) {
    Q++;
    P++;
    l = r = Q;
    val = K;
    cur = P;
    update1(1,1,c);
}

long long calculate(int P, int Q, int U, int V) {
    l = Q+1;
    r = V+1;
    ll ans = 0;
    up = P+1;
    dw = U+1;
    if(type)ans = get(1,1,c);
    else{
        for(int i=P+1;i<=U+1;i++){
            cur = i;
            ans = gcd2(ans,get(1,1,c));
        }
    }
    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]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 0 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 3 ms 896 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 1546 ms 20808 KB Output is correct
5 Correct 814 ms 21116 KB Output is correct
6 Correct 1383 ms 21752 KB Output is correct
7 Correct 1426 ms 21388 KB Output is correct
8 Correct 1163 ms 19988 KB Output is correct
9 Correct 1368 ms 21676 KB Output is correct
10 Correct 1177 ms 21112 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 4 ms 896 KB Output is correct
11 Correct 3 ms 896 KB Output is correct
12 Correct 3585 ms 43928 KB Output is correct
13 Correct 5051 ms 37644 KB Output is correct
14 Correct 3608 ms 5576 KB Output is correct
15 Correct 8932 ms 106044 KB Output is correct
16 Correct 12276 ms 129980 KB Output is correct
17 Correct 6173 ms 116328 KB Output is correct
18 Execution timed out 13044 ms 129580 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 4 ms 896 KB Output is correct
11 Correct 3 ms 896 KB Output is correct
12 Correct 1650 ms 20964 KB Output is correct
13 Correct 698 ms 21368 KB Output is correct
14 Correct 1281 ms 21688 KB Output is correct
15 Correct 1452 ms 21496 KB Output is correct
16 Correct 1170 ms 19940 KB Output is correct
17 Correct 1353 ms 21456 KB Output is correct
18 Correct 1158 ms 20968 KB Output is correct
19 Correct 3650 ms 44048 KB Output is correct
20 Correct 4834 ms 37580 KB Output is correct
21 Correct 3427 ms 5616 KB Output is correct
22 Correct 7903 ms 106356 KB Output is correct
23 Correct 12050 ms 130052 KB Output is correct
24 Correct 5893 ms 116324 KB Output is correct
25 Execution timed out 13036 ms 130424 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 6 ms 1280 KB Output is correct
3 Correct 7 ms 1280 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 1280 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 6 ms 1280 KB Output is correct
10 Correct 4 ms 896 KB Output is correct
11 Correct 2 ms 896 KB Output is correct
12 Correct 1602 ms 20868 KB Output is correct
13 Correct 800 ms 21180 KB Output is correct
14 Correct 1254 ms 21720 KB Output is correct
15 Correct 1347 ms 21500 KB Output is correct
16 Correct 1155 ms 19908 KB Output is correct
17 Correct 1350 ms 21624 KB Output is correct
18 Correct 1199 ms 21120 KB Output is correct
19 Correct 3720 ms 43872 KB Output is correct
20 Correct 4915 ms 37600 KB Output is correct
21 Correct 3184 ms 5600 KB Output is correct
22 Correct 8163 ms 105948 KB Output is correct
23 Correct 12485 ms 129828 KB Output is correct
24 Correct 6230 ms 116032 KB Output is correct
25 Execution timed out 13045 ms 131188 KB Time limit exceeded
26 Halted 0 ms 0 KB -