oj.uz

답안 #402759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402759 2021-05-12T10:41:04 Z ACmachine 게임 (IOI13_game) C++17
37 / 100
 13000 ms 5240 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);
    REP(i, R + 1){
      grid[i] = new treap(-1, 0);
    }
}
 
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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 256 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 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 1 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 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 1548 ms 5060 KB Output is correct
5 Correct 605 ms 5216 KB Output is correct
6 Correct 1936 ms 2012 KB Output is correct
7 Correct 2275 ms 1892 KB Output is correct
8 Correct 1471 ms 2340 KB Output is correct
9 Correct 2165 ms 1740 KB Output is correct
10 Correct 1898 ms 1476 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 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 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 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 13086 ms 3600 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 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 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 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 1419 ms 5060 KB Output is correct
13 Correct 553 ms 5240 KB Output is correct
14 Correct 1888 ms 2096 KB Output is correct
15 Correct 2261 ms 1604 KB Output is correct
16 Correct 1501 ms 2296 KB Output is correct
17 Correct 2182 ms 2020 KB Output is correct
18 Correct 1856 ms 1432 KB Output is correct
19 Execution timed out 13005 ms 3544 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 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 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 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 1447 ms 4880 KB Output is correct
13 Correct 529 ms 5188 KB Output is correct
14 Correct 1905 ms 1928 KB Output is correct
15 Correct 2276 ms 1860 KB Output is correct
16 Correct 1485 ms 2252 KB Output is correct
17 Correct 2149 ms 1828 KB Output is correct
18 Correct 1870 ms 1544 KB Output is correct
19 Execution timed out 13055 ms 3484 KB Time limit exceeded
20 Halted 0 ms 0 KB -