oj.uz

Submission #99096

# Submission time Handle Problem Language Result Execution time Memory
99096 2019-02-28T14:48:27 Z figter001 Game (IOI13_game) C++14
37 / 100
 13000 ms 157644 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[4100];
    node(){
        memset(sub,0,sizeof(sub));
    }
}seg[4100];

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 108 ms 131960 KB Output is correct
2 Correct 113 ms 132044 KB Output is correct
3 Correct 109 ms 131960 KB Output is correct
4 Correct 104 ms 131960 KB Output is correct
5 Correct 111 ms 131908 KB Output is correct
6 Correct 115 ms 131932 KB Output is correct
7 Correct 114 ms 131880 KB Output is correct
8 Correct 109 ms 131832 KB Output is correct
9 Correct 110 ms 131940 KB Output is correct
10 Correct 126 ms 131932 KB Output is correct
11 Correct 115 ms 131840 KB Output is correct
12 Correct 107 ms 131912 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 131960 KB Output is correct
2 Correct 114 ms 132048 KB Output is correct
3 Correct 123 ms 131960 KB Output is correct
4 Correct 1717 ms 156460 KB Output is correct
5 Correct 971 ms 156408 KB Output is correct
6 Correct 1556 ms 157644 KB Output is correct
7 Correct 1537 ms 157172 KB Output is correct
8 Correct 1222 ms 155644 KB Output is correct
9 Correct 1460 ms 157320 KB Output is correct
10 Correct 1217 ms 156848 KB Output is correct
11 Correct 124 ms 131884 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 131972 KB Output is correct
2 Correct 117 ms 131832 KB Output is correct
3 Correct 107 ms 131960 KB Output is correct
4 Correct 110 ms 131920 KB Output is correct
5 Correct 111 ms 131840 KB Output is correct
6 Correct 109 ms 131984 KB Output is correct
7 Correct 108 ms 131960 KB Output is correct
8 Correct 121 ms 131880 KB Output is correct
9 Correct 123 ms 131960 KB Output is correct
10 Correct 110 ms 131932 KB Output is correct
11 Correct 110 ms 131908 KB Output is correct
12 Correct 3526 ms 140076 KB Output is correct
13 Correct 5483 ms 136572 KB Output is correct
14 Correct 4395 ms 136892 KB Output is correct
15 Correct 8553 ms 137172 KB Output is correct
16 Correct 12064 ms 136908 KB Output is correct
17 Correct 6172 ms 137748 KB Output is correct
18 Execution timed out 13058 ms 137428 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 131960 KB Output is correct
2 Correct 112 ms 131832 KB Output is correct
3 Correct 121 ms 131844 KB Output is correct
4 Correct 107 ms 132020 KB Output is correct
5 Correct 103 ms 131832 KB Output is correct
6 Correct 111 ms 131960 KB Output is correct
7 Correct 106 ms 131960 KB Output is correct
8 Correct 106 ms 131940 KB Output is correct
9 Correct 108 ms 131932 KB Output is correct
10 Correct 111 ms 131940 KB Output is correct
11 Correct 110 ms 131964 KB Output is correct
12 Correct 1796 ms 156388 KB Output is correct
13 Correct 955 ms 156316 KB Output is correct
14 Correct 1509 ms 157380 KB Output is correct
15 Correct 1468 ms 157492 KB Output is correct
16 Correct 1144 ms 155624 KB Output is correct
17 Correct 1577 ms 157308 KB Output is correct
18 Correct 1462 ms 156860 KB Output is correct
19 Correct 4051 ms 139932 KB Output is correct
20 Correct 5443 ms 136644 KB Output is correct
21 Correct 3924 ms 137208 KB Output is correct
22 Correct 8913 ms 137096 KB Output is correct
23 Correct 12318 ms 136864 KB Output is correct
24 Correct 6372 ms 138260 KB Output is correct
25 Execution timed out 13023 ms 137528 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 131960 KB Output is correct
2 Correct 113 ms 131956 KB Output is correct
3 Correct 128 ms 131832 KB Output is correct
4 Correct 115 ms 131912 KB Output is correct
5 Correct 121 ms 131944 KB Output is correct
6 Correct 112 ms 132060 KB Output is correct
7 Correct 125 ms 131944 KB Output is correct
8 Correct 112 ms 131832 KB Output is correct
9 Correct 108 ms 131832 KB Output is correct
10 Correct 117 ms 131932 KB Output is correct
11 Correct 112 ms 131960 KB Output is correct
12 Correct 1833 ms 156380 KB Output is correct
13 Correct 954 ms 156348 KB Output is correct
14 Correct 1533 ms 157552 KB Output is correct
15 Correct 1539 ms 157432 KB Output is correct
16 Correct 1253 ms 155516 KB Output is correct
17 Correct 1567 ms 157304 KB Output is correct
18 Correct 1271 ms 156768 KB Output is correct
19 Correct 4027 ms 140228 KB Output is correct
20 Correct 5155 ms 136536 KB Output is correct
21 Correct 4380 ms 137304 KB Output is correct
22 Correct 8713 ms 137036 KB Output is correct
23 Correct 12369 ms 136904 KB Output is correct
24 Correct 6049 ms 138204 KB Output is correct
25 Execution timed out 13059 ms 136444 KB Time limit exceeded
26 Halted 0 ms 0 KB -