oj.uz

Submission #388051

# Submission time Handle Problem Language Result Execution time Memory
388051 2021-04-09T19:56:13 Z ivan24 Game (IOI13_game) C++14
37 / 100
 13000 ms 43992 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
#define F first
#define S second
typedef vector<ii> vii;
typedef vector<vii> vvii;

long long gcd2(long long X, long long Y) {
    //cout << X << ' ' << Y << ": ";
    long long tmp;
    if (X < Y) swap(X,Y);
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    //cout << X << endl;
    return X;
}

class SegmentTree {
private:
    ll n;
    vi data;
    vector<long long int> st;

    ll left (ll x){
        return (x << 1);
    }
    ll right(ll x){
        return ((x << 1) + 1);
    }
    void build (ll i, ll l, ll r){
        if (l == r){
            st[i] = data[l];
        }else{
            ll m = (l+r)/2;
            build(left(i),l,m);
            build(right(i),m+1,r);
            st[i] = gcd2(st[left(i)], st[right(i)]);
        }
    }
    long long int query (ll i, ll l, ll r, ll ql, ll qr){
        if (qr >= r && l >= ql){
            return st[i];
        }else if (ql > r || l > qr){
            return 0;
        }else{
            ll m = (l+r)/2;
            long long int ansl = query(left(i),l,m,ql,qr);
            long long int ansr = query(right(i),m+1,r,ql,qr);
            return gcd2(ansl,ansr);
        }
    }
    void update (ll i, ll l, ll r, ll idx, long long int val){
        if (l == idx && r == idx){
            st[i] = val;
        }else if (r >= idx && idx >= l){
            ll m = (l+r)/2;
            update(left(i),l,m,idx,val);
            update(right(i),m+1,r,idx,val);
            st[i] = gcd2(st[left(i)], st[right(i)]);
        }
    }
public:
    SegmentTree (const vi& _data): data(_data), n(_data.size()){
        st.assign(4*n,0);
        //build(1,0,n-1);
    }
    void update (ll idx, long long int val){
        update(1,0,n-1,idx,val);
    }
    long long int query (ll ql, ll qr){
        return query(1,0,n-1,ql,qr);
    }
    void print(){
        for (auto i: st){ cout << i << ' '; }
        cout << endl;
    }
};

vector<SegmentTree> grid;

void init(int r, int c) {
    /* ... */
    vi te;
    te.assign(c,0);
    grid.assign(r,SegmentTree(te));
}

void update(int p, int q, long long k) {
    /* ... */
    grid[p].update(q,k);
}

long long calculate(int p, int q, int u, int v) {
    /* ... */
    long long int ans = 0;
    for (ll i = p; u >= i; i++){
        //cout << "grid[i].query(q,v): " << ' ';
        //cout << grid[i].query(q,v) << endl;
        ans = gcd2(ans,grid[i].query(q,v));
    }
    return ans;
}

Compilation message

game.cpp: In constructor 'SegmentTree::SegmentTree(const vi&)':
game.cpp:29:8: warning: 'SegmentTree::data' will be initialized after [-Wreorder]
   29 |     vi data;
      |        ^~~~
game.cpp:28:8: warning:   'll SegmentTree::n' [-Wreorder]
   28 |     ll n;
      |        ^
game.cpp:71:5: warning:   when initialized here [-Wreorder]
   71 |     SegmentTree (const vi& _data): data(_data), n(_data.size()){
      |     ^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 544 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 904 ms 43936 KB Output is correct
5 Correct 548 ms 43844 KB Output is correct
6 Correct 840 ms 41392 KB Output is correct
7 Correct 853 ms 41076 KB Output is correct
8 Correct 726 ms 41412 KB Output is correct
9 Correct 859 ms 41220 KB Output is correct
10 Correct 798 ms 40800 KB Output is correct
11 Correct 0 ms 292 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Execution timed out 13043 ms 38096 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 982 ms 43980 KB Output is correct
13 Correct 558 ms 43796 KB Output is correct
14 Correct 796 ms 41276 KB Output is correct
15 Correct 864 ms 41136 KB Output is correct
16 Correct 713 ms 41392 KB Output is correct
17 Correct 826 ms 41056 KB Output is correct
18 Correct 765 ms 40700 KB Output is correct
19 Execution timed out 13076 ms 38284 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1055 ms 43992 KB Output is correct
13 Correct 571 ms 43736 KB Output is correct
14 Correct 898 ms 41204 KB Output is correct
15 Correct 927 ms 40956 KB Output is correct
16 Correct 789 ms 41404 KB Output is correct
17 Correct 910 ms 41096 KB Output is correct
18 Correct 824 ms 40764 KB Output is correct
19 Execution timed out 13089 ms 38256 KB Time limit exceeded
20 Halted 0 ms 0 KB -