oj.uz

Submission #62906

# Submission time Handle Problem Language Result Execution time Memory
62906 2018-07-30T18:16:31 Z mhnd Game (IOI13_game) C++14
37 / 100
 13000 ms 220048 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[2*2010+123];
    node(){
        memset(sub,0,sizeof(sub));
    }
}seg[2*2010+123];

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);
    //up = dw = 1;
    //cout << get(1,1,c) << endl;
}

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 98 ms 134648 KB Output is correct
2 Correct 106 ms 134768 KB Output is correct
3 Correct 117 ms 134800 KB Output is correct
4 Correct 118 ms 134800 KB Output is correct
5 Correct 124 ms 134800 KB Output is correct
6 Correct 114 ms 134800 KB Output is correct
7 Correct 97 ms 134812 KB Output is correct
8 Correct 121 ms 134996 KB Output is correct
9 Correct 104 ms 134996 KB Output is correct
10 Correct 104 ms 134996 KB Output is correct
11 Correct 115 ms 134996 KB Output is correct
12 Correct 106 ms 134996 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 134996 KB Output is correct
2 Correct 103 ms 134996 KB Output is correct
3 Correct 105 ms 134996 KB Output is correct
4 Correct 1726 ms 159492 KB Output is correct
5 Correct 968 ms 163932 KB Output is correct
6 Correct 1365 ms 168816 KB Output is correct
7 Correct 1810 ms 173388 KB Output is correct
8 Correct 1273 ms 175240 KB Output is correct
9 Correct 1700 ms 176564 KB Output is correct
10 Correct 1205 ms 176564 KB Output is correct
11 Correct 99 ms 176564 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 176564 KB Output is correct
2 Correct 129 ms 176564 KB Output is correct
3 Correct 121 ms 176564 KB Output is correct
4 Correct 113 ms 176564 KB Output is correct
5 Correct 122 ms 176564 KB Output is correct
6 Correct 113 ms 176564 KB Output is correct
7 Correct 122 ms 176564 KB Output is correct
8 Correct 100 ms 176564 KB Output is correct
9 Correct 122 ms 176564 KB Output is correct
10 Correct 101 ms 176564 KB Output is correct
11 Correct 99 ms 176564 KB Output is correct
12 Correct 3451 ms 176564 KB Output is correct
13 Correct 5424 ms 176564 KB Output is correct
14 Correct 4142 ms 176564 KB Output is correct
15 Correct 9196 ms 176564 KB Output is correct
16 Execution timed out 13017 ms 176564 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 176564 KB Output is correct
2 Correct 109 ms 176564 KB Output is correct
3 Correct 117 ms 176564 KB Output is correct
4 Correct 111 ms 176564 KB Output is correct
5 Correct 103 ms 176564 KB Output is correct
6 Correct 109 ms 176564 KB Output is correct
7 Correct 113 ms 176564 KB Output is correct
8 Correct 104 ms 176564 KB Output is correct
9 Correct 119 ms 176564 KB Output is correct
10 Correct 131 ms 176564 KB Output is correct
11 Correct 118 ms 176564 KB Output is correct
12 Correct 1623 ms 192752 KB Output is correct
13 Correct 957 ms 193008 KB Output is correct
14 Correct 1514 ms 193516 KB Output is correct
15 Correct 1474 ms 193516 KB Output is correct
16 Correct 1203 ms 193516 KB Output is correct
17 Correct 1582 ms 193520 KB Output is correct
18 Correct 1329 ms 193520 KB Output is correct
19 Correct 4154 ms 193520 KB Output is correct
20 Correct 5627 ms 193520 KB Output is correct
21 Correct 4131 ms 193520 KB Output is correct
22 Correct 9319 ms 193520 KB Output is correct
23 Correct 12926 ms 193576 KB Output is correct
24 Correct 6852 ms 199196 KB Output is correct
25 Execution timed out 13044 ms 199764 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 199764 KB Output is correct
2 Correct 118 ms 199764 KB Output is correct
3 Correct 118 ms 199764 KB Output is correct
4 Correct 128 ms 199764 KB Output is correct
5 Correct 115 ms 199764 KB Output is correct
6 Correct 116 ms 199764 KB Output is correct
7 Correct 108 ms 199764 KB Output is correct
8 Correct 101 ms 199764 KB Output is correct
9 Correct 117 ms 199764 KB Output is correct
10 Correct 105 ms 199764 KB Output is correct
11 Correct 105 ms 199764 KB Output is correct
12 Correct 1619 ms 219208 KB Output is correct
13 Correct 909 ms 219744 KB Output is correct
14 Correct 1443 ms 220048 KB Output is correct
15 Correct 1481 ms 220048 KB Output is correct
16 Correct 1340 ms 220048 KB Output is correct
17 Correct 1407 ms 220048 KB Output is correct
18 Correct 1261 ms 220048 KB Output is correct
19 Correct 3727 ms 220048 KB Output is correct
20 Correct 5870 ms 220048 KB Output is correct
21 Correct 3595 ms 220048 KB Output is correct
22 Correct 9640 ms 220048 KB Output is correct
23 Execution timed out 13035 ms 220048 KB Time limit exceeded
24 Halted 0 ms 0 KB -