Submission #591065

#	Time	Username	Problem	Language	Result	Execution time	Memory
591065		TimDee	게임 (IOI13_game)	C++14	37 / 100	13096 ms	29080 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define ll long long

struct segtree {
    
    vector<ll> tree;
    ll size;
    ll n;
    ll neutral;
    
    void put(ll i, ll v) {
        
        tree[i]=v;
        
    }
    
    ll combine(ll i, ll j) {
        //for min
        return __gcd(i,j);
        //for max
        //return max(i,j);
        //for sum
        //return i+j;
    }
 
    void update(ll x, ll l, ll r, ll i) {
        
        if (i>=r || i<l) return;
        if (r-l == 1) return;
        
        ll mid=(l+r)/2;
        update(2*x+1,l,mid,i);
        update(2*x+2,mid,r,i);
        
        tree[x]=combine(tree[2*x+1],tree[2*x+2]);
    }
    
    void update(ll x, ll l, ll r) {
 
        if (r-l == 1) return;
        
        ll mid=(l+r)/2;
        update(2*x+1,l,mid);
        update(2*x+2,mid,r);
        
        tree[x]=combine(tree[2*x+1],tree[2*x+2]);
    }
    
    segtree(vector<ll>&a, ll neutr) {
        
        n=a.size();
       
        //for min
        //neutral = inf;
        //for max
        //neutral = -inf;
        //for sum
        //neutral = 0;

        neutral = neutr;

        size=1;
        while (size < n) size*=2;
        
        tree.assign(2*size-1,neutral);
        
        for(ll i=0; i<n; ++i) put(size-1+i,a[i]);
        
        update(0,0,size);
        
    }
    
    void clear() {
        
        tree.assign(2*size-1,0);
        
    }
    
    ll calc(ll x, ll lx, ll rx, ll l, ll r) {
        
        if (lx>=r || rx<=l) return neutral;
        if (lx>=l && rx<=r) return tree[x];
        
        ll mid=(lx+rx)/2;
        ll a=calc(2*x+1,lx,mid,l,r),
        b=calc(2*x+2,mid,rx,l,r);
        return combine(a,b);
    }
    
    ll query(ll l, ll r) {
        if (l>=r) return neutral;
        return calc(0,0,size,l,r);
    }
    
    void set(ll i, ll v) {
        
        put(size-1+i,v);
        update(0, 0, size, i);
        
    }
    
    void prll() {
        
        cout<<"TREE: \n";
        ll z=0;
        while (z<tree.size()) {
            for (ll i=z; i<2*z+1; i++) cout<<tree[i]<<' ';
            cout<<'\n';
            z=z*2+1;
        }
        cout<<'\n';
        
    }
    
};

vector<segtree> V;

void init (int r, int c) {
    vector<ll> a(c,0);
    segtree zero(a,0);
    V.assign(r,zero);
}

//map<ll,map<ll,ll>> m;
//set<ll> s;
//map<ll,set<ll>> A;
void update(int x, int y, ll v) {
    V[x].set(y,v);
}

ll calculate(int a, int b, int c, int d) {
    ll ans=0;
    for (ll i=a; i<=c; ++i) {
        ans=__gcd(ans,V[i].query(b,d+1));
    }
    return ans;
}

Compilation message (stderr)

game.cpp: In member function 'void segtree::prll()':
game.cpp:109:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         while (z<tree.size()) {
      |                ~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20