oj.uz

Submission #402724

# Submission time Handle Problem Language Result Execution time Memory
402724 2021-05-12T09:51:21 Z ACmachine Game (IOI13_game) C++17
37 / 100
 13000 ms 9172 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)

const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;

template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "[";  REP(i, U) out << v[i] << ", ";  out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}

template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }



long long gcd2(long long X, long long Y) {
    if(X == 0) return Y;
    if(Y == 0) return X;
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct treap{
    ll val; int key;
    ll res;
    int y;
    array<treap*, 2> ch;
    treap(int _key, ll _val) : key(_key), val(_val), y(rand()), res(val){
        ch = {NULL, NULL};
    }
};

vector<treap*> grid;
void recalc(treap *t){
    if(t == NULL) return;
    t->res = t->val;
    REP(i, 2){
        if(t->ch[i] != NULL)
            t->res = gcd2(t->res, t->ch[i]->res);
    }
    return;
}
ll getres(treap* t){
    return (t == NULL ? 0 : t->res);
}
pair<treap*, treap*> split(treap* t, int key){ // all < key
    if(t == NULL)
        return {NULL, NULL};
    if(t->key < key){
        auto pa = split(t->ch[1], key);
        t->ch[1] = pa.ff;
        recalc(t);
        return {t, pa.ss};
    }
    else{
        auto pa = split(t->ch[0], key);
        t->ch[0] = pa.ss;
        recalc(t);
        return {pa.ff, t};
    }
}
treap* merge(treap* f, treap *s){
    if(f == NULL) return s;
    if(s == NULL) return f;
    if(f->y >= s->y){
        f->ch[1] = merge(f->ch[1], s);
        recalc(f);
        return f;
    }
    else{
        s->ch[0] = merge(f, s->ch[0]);
        recalc(s);
        return s;
    }
}
treap* insert(treap* t, treap *s){ // second add to treapu t
    if(t == NULL) {
        return s;
    }
    auto paf = split(t, s->key);
    auto pas = split(paf.ss, s->key + 1);
    t = merge(paf.ff, merge(s, pas.ss));
    return t;
}
ll query_treap(treap* &t, int l, int r){
    if(t == NULL) return 0ll;
    auto pa = split(t, l);
    auto pa2 = split(pa.ss, r);
    ll res = getres(pa2.ff);
    t = merge(pa.ff, merge(pa2.ff, pa2.ss));
    return res;
}
void init(int R, int C) {
    srand(time(NULL));
    grid.resize(R + 1, NULL);
}

void update(int P, int Q, long long K) {
    treap *s = new treap(Q, K);
    grid[P] = insert(grid[P], s);
}

long long calculate(int P, int Q, int U, int V) {
    ll res = 0;
    FOR(i, P, U + 1, 1){
        res = gcd2(res, query_treap(grid[i], Q, V + 1));
    }
    return res;
}

Compilation message

game.cpp: In constructor 'treap::treap(int, ll)':
game.cpp:73:17: warning: 'treap::key' will be initialized after [-Wreorder]
   73 |     ll val; int key;
      |                 ^~~
game.cpp:73:8: warning:   'll treap::val' [-Wreorder]
   73 |     ll val; int key;
      |        ^~~
game.cpp:77:5: warning:   when initialized here [-Wreorder]
   77 |     treap(int _key, ll _val) : key(_key), val(_val), y(rand()), res(val){
      |     ^~~~~
game.cpp:75:9: warning: 'treap::y' will be initialized after [-Wreorder]
   75 |     int y;
      |         ^
game.cpp:74:8: warning:   'll treap::res' [-Wreorder]
   74 |     ll res;
      |        ^~~
game.cpp:77:5: warning:   when initialized here [-Wreorder]
   77 |     treap(int _key, ll _val) : key(_key), val(_val), y(rand()), res(val){
      |     ^~~~~

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 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1405 ms 6688 KB Output is correct
5 Correct 450 ms 9172 KB Output is correct
6 Correct 1983 ms 6536 KB Output is correct
7 Correct 2420 ms 6252 KB Output is correct
8 Correct 1513 ms 6504 KB Output is correct
9 Correct 2257 ms 6420 KB Output is correct
10 Correct 1859 ms 6020 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 204 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 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Execution timed out 13059 ms 5828 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1360 ms 6736 KB Output is correct
13 Correct 455 ms 9156 KB Output is correct
14 Correct 1898 ms 6708 KB Output is correct
15 Correct 2359 ms 6444 KB Output is correct
16 Correct 1474 ms 6584 KB Output is correct
17 Correct 2219 ms 6504 KB Output is correct
18 Correct 1917 ms 5960 KB Output is correct
19 Execution timed out 13098 ms 7368 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 204 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 288 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1374 ms 6688 KB Output is correct
13 Correct 466 ms 9132 KB Output is correct
14 Correct 1993 ms 6544 KB Output is correct
15 Correct 2366 ms 6356 KB Output is correct
16 Correct 1491 ms 6420 KB Output is correct
17 Correct 2140 ms 6428 KB Output is correct
18 Correct 1902 ms 5964 KB Output is correct
19 Execution timed out 13063 ms 7156 KB Time limit exceeded
20 Halted 0 ms 0 KB -