Submission #388049

#	Time	Username	Problem	Language	Result	Execution time	Memory
388049		ivan24	Game (IOI13_game)	C++14	0 / 100	1 ms	280 KiB

game

#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;
    vi 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;
            ll ansl = query(left(i),l,m,ql,qr);
            ll 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){
            data[l] = 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);
    }
    ll 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 (stderr)

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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20