oj.uz

Submission #591065

# Submission time Handle Problem Language Result Execution time Memory
591065 2022-07-06T19:39:09 Z TimDee Game (IOI13_game) C++14
37 / 100
 13000 ms 29080 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 0 ms 300 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 726 ms 27036 KB Output is correct
5 Correct 422 ms 29016 KB Output is correct
6 Correct 650 ms 26552 KB Output is correct
7 Correct 623 ms 26200 KB Output is correct
8 Correct 523 ms 26664 KB Output is correct
9 Correct 586 ms 26492 KB Output is correct
10 Correct 498 ms 25920 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 428 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 424 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Execution timed out 13076 ms 18284 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 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 668 ms 27168 KB Output is correct
13 Correct 424 ms 29028 KB Output is correct
14 Correct 567 ms 26536 KB Output is correct
15 Correct 599 ms 26384 KB Output is correct
16 Correct 482 ms 26604 KB Output is correct
17 Correct 635 ms 26488 KB Output is correct
18 Correct 554 ms 26124 KB Output is correct
19 Execution timed out 13060 ms 19160 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 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 751 ms 27160 KB Output is correct
13 Correct 424 ms 29080 KB Output is correct
14 Correct 590 ms 26576 KB Output is correct
15 Correct 600 ms 26372 KB Output is correct
16 Correct 495 ms 26668 KB Output is correct
17 Correct 633 ms 26372 KB Output is correct
18 Correct 527 ms 25976 KB Output is correct
19 Execution timed out 13096 ms 19056 KB Time limit exceeded
20 Halted 0 ms 0 KB -