oj.uz

Submission #62907

# Submission time Handle Problem Language Result Execution time Memory
62907 2018-07-30T18:17:48 Z mhnd Game (IOI13_game) C++11
37 / 100
 13000 ms 155984 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 105 ms 134648 KB Output is correct
2 Correct 105 ms 134672 KB Output is correct
3 Correct 105 ms 134700 KB Output is correct
4 Correct 108 ms 134884 KB Output is correct
5 Correct 116 ms 134884 KB Output is correct
6 Correct 105 ms 134884 KB Output is correct
7 Correct 101 ms 134884 KB Output is correct
8 Correct 98 ms 134884 KB Output is correct
9 Correct 104 ms 134884 KB Output is correct
10 Correct 101 ms 134884 KB Output is correct
11 Correct 100 ms 134884 KB Output is correct
12 Correct 103 ms 134884 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 134888 KB Output is correct
2 Correct 100 ms 134888 KB Output is correct
3 Correct 99 ms 134888 KB Output is correct
4 Correct 1754 ms 155080 KB Output is correct
5 Correct 1136 ms 155668 KB Output is correct
6 Correct 1585 ms 155956 KB Output is correct
7 Correct 1749 ms 155956 KB Output is correct
8 Correct 1365 ms 155956 KB Output is correct
9 Correct 1589 ms 155956 KB Output is correct
10 Correct 1210 ms 155956 KB Output is correct
11 Correct 103 ms 155956 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 155956 KB Output is correct
2 Correct 104 ms 155956 KB Output is correct
3 Correct 116 ms 155956 KB Output is correct
4 Correct 102 ms 155956 KB Output is correct
5 Correct 100 ms 155956 KB Output is correct
6 Correct 102 ms 155956 KB Output is correct
7 Correct 98 ms 155956 KB Output is correct
8 Correct 109 ms 155956 KB Output is correct
9 Correct 104 ms 155956 KB Output is correct
10 Correct 100 ms 155956 KB Output is correct
11 Correct 116 ms 155956 KB Output is correct
12 Correct 3557 ms 155956 KB Output is correct
13 Correct 5709 ms 155956 KB Output is correct
14 Correct 4380 ms 155956 KB Output is correct
15 Correct 8780 ms 155956 KB Output is correct
16 Execution timed out 13010 ms 155956 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 155956 KB Output is correct
2 Correct 117 ms 155956 KB Output is correct
3 Correct 123 ms 155956 KB Output is correct
4 Correct 114 ms 155956 KB Output is correct
5 Correct 113 ms 155956 KB Output is correct
6 Correct 131 ms 155956 KB Output is correct
7 Correct 113 ms 155956 KB Output is correct
8 Correct 125 ms 155956 KB Output is correct
9 Correct 103 ms 155956 KB Output is correct
10 Correct 101 ms 155956 KB Output is correct
11 Correct 104 ms 155956 KB Output is correct
12 Correct 1646 ms 155956 KB Output is correct
13 Correct 995 ms 155956 KB Output is correct
14 Correct 1343 ms 155956 KB Output is correct
15 Correct 1542 ms 155956 KB Output is correct
16 Correct 1112 ms 155956 KB Output is correct
17 Correct 1484 ms 155976 KB Output is correct
18 Correct 1199 ms 155976 KB Output is correct
19 Correct 4262 ms 155976 KB Output is correct
20 Correct 6089 ms 155976 KB Output is correct
21 Correct 4035 ms 155976 KB Output is correct
22 Correct 9584 ms 155976 KB Output is correct
23 Execution timed out 13092 ms 155976 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 155976 KB Output is correct
2 Correct 123 ms 155976 KB Output is correct
3 Correct 121 ms 155976 KB Output is correct
4 Correct 100 ms 155976 KB Output is correct
5 Correct 103 ms 155976 KB Output is correct
6 Correct 102 ms 155976 KB Output is correct
7 Correct 113 ms 155976 KB Output is correct
8 Correct 98 ms 155976 KB Output is correct
9 Correct 100 ms 155976 KB Output is correct
10 Correct 128 ms 155976 KB Output is correct
11 Correct 103 ms 155976 KB Output is correct
12 Correct 1711 ms 155976 KB Output is correct
13 Correct 889 ms 155976 KB Output is correct
14 Correct 1280 ms 155984 KB Output is correct
15 Correct 1603 ms 155984 KB Output is correct
16 Correct 1098 ms 155984 KB Output is correct
17 Correct 1415 ms 155984 KB Output is correct
18 Correct 1328 ms 155984 KB Output is correct
19 Correct 4235 ms 155984 KB Output is correct
20 Correct 5924 ms 155984 KB Output is correct
21 Correct 3918 ms 155984 KB Output is correct
22 Correct 9008 ms 155984 KB Output is correct
23 Execution timed out 13023 ms 155984 KB Time limit exceeded
24 Halted 0 ms 0 KB -