oj.uz

답안 #330064

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
330064 2020-11-23T15:59:26 Z wiwiho 게임 (IOI13_game) C++14
63 / 100
 1797 ms 256000 KB 
#include "game.h"

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) (((a) + (b) - 1) / (b))
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

struct Node2D{
    int l = -1, r = -1, rt = -1;
};

struct Node1D{
    int l = -1, r = -1;
    ll v = 0;
};

vector<Node2D> st2d(1e7);
vector<Node1D> st1d(4e6);
int ts1d = 0, ts2d = 1;

int n, m;

void pull(int id){
    auto &st = st1d;
    if(st[id].l == -1 && st[id].r == -1) return;
    else if(st[id].l == -1) st[id].v = st[st[id].r].v;
    else if(st[id].r == -1) st[id].v = st[st[id].l].v;
    else st[id].v = __gcd(st[st[id].l].v, st[st[id].r].v);
//    cerr << "pull1d " << id << " " << (st[id].l == -1 ? 0 : st[st[id].l].v) << " " << (st[id].r == -1 ? 0 : st[st[id].r].v) << " " << st[id].v << "\n";
}

int modify1D(int pos, ll v, int L, int R, int id){
    auto &st = st1d;
    if(id == -1) id = ts1d++;
//    cerr << "modify1D " << pos << " " << v << " " << L << " " << R << " " << id << "\n";
    if(L == R){
        st[id].v = v;
        return id;
    }
    int M = (L + R) / 2;
    if(pos <= M) st[id].l = modify1D(pos, v, L, M, st[id].l);
    else st[id].r = modify1D(pos, v, M + 1, R, st[id].r);
    pull(id);
    return id;
}

ll query1D(int l, int r, int L, int R, int id){
//    cerr << "query1D " << l << " " << r << " " << L << " " << R << " " << id << " " << (id == -1 ? 0 : st1d[id].v) << "\n";
    if(id == -1) return 0;
    auto &st = st1d;
    if(l == L && r == R){
        return st[id].v;
    }
    int M = (L + R) / 2;
    if(r <= M) return query1D(l, r, L, M, st[id].l);
    else if(l > M) return query1D(l, r, M + 1, R, st[id].r);
    else return __gcd(query1D(l, M, L, M, st[id].l), query1D(M + 1, r, M + 1, R, st[id].r));
}

void pull(int id, int y){
//    cerr << "pull2d " << id << " " << y << "\n";
    auto &st = st2d;
    if(st[id].l == -1 && st[id].r == -1) return;
    else if(st[id].l == -1) st[id].rt = modify1D(y, query1D(y, y, 1, m, st[st[id].r].rt), 1, m, st[id].rt);
    else if(st[id].r == -1) st[id].rt = modify1D(y, query1D(y, y, 1, m, st[st[id].l].rt), 1, m, st[id].rt);
    else st[id].rt = modify1D(y, __gcd(query1D(y, y, 1, m, st[st[id].l].rt), query1D(y, y, 1, m, st[st[id].r].rt)), 1, m, st[id].rt);
}

int modify2D(int x, int y, ll v, int L, int R, int id){
    auto& st = st2d;
    if(id == -1) id = ts2d++;
//    cerr << "modify2D " << x << " " << y << " " << v << " " << L << " " << R << " " << id << "\n";
    if(L == R){
        st[id].rt = modify1D(y, v, 1, m, st[id].rt);
        return id;
    }
    int M = (L + R) / 2;
    if(x <= M) st[id].l = modify2D(x, y, v, L, M, st[id].l);
    else st[id].r = modify2D(x, y, v, M + 1, R, st[id].r);
    pull(id, y);
    return id;
}

ll query2D(int x1, int y1, int x2, int y2, int L, int R, int id){
//    cerr << "query2D " << x1 << " " << y1 << " " << x2 << " " << y2 << " " << L << " " << R << " " << id << "\n";
    if(id == -1) return 0;
    auto &st = st2d;
    if(L == x1 && R == x2){
        return query1D(y1, y2, 1, m, st[id].rt);
    }
    int M = (L + R) / 2;
    if(x2 <= M) return query2D(x1, y1, x2, y2, L, M, st[id].l);
    else if(x1 > M) return query2D(x1, y1, x2, y2, M + 1, R, st[id].r);
    else{
        return __gcd(query2D(x1, y1, M, y2, L, M, st[id].l), query2D(M + 1, y1, x2, y2, M + 1, R, st[id].r));
    }
}

void init(int R, int C) {
    n = R;
    m = C;
}

void update(int P, int Q, long long K) {
//    cerr << "upd " << P << " " << Q << " " << K << "\n";
    P++; Q++;
    modify2D(P, Q, K, 1, n, 0);
}

long long calculate(int P, int Q, int U, int V) {
//    cerr << "qry " << P << " " << Q << " " << U << " " << V << "\n";
    P++; Q++; U++; V++;
    return query2D(P, Q, U, V, 1, n, 0);
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 180332 KB Output is correct
2 Correct 114 ms 180332 KB Output is correct
3 Correct 115 ms 180332 KB Output is correct
4 Correct 115 ms 180332 KB Output is correct
5 Correct 114 ms 180460 KB Output is correct
6 Correct 116 ms 180332 KB Output is correct
7 Correct 115 ms 180332 KB Output is correct
8 Correct 114 ms 180280 KB Output is correct
9 Correct 113 ms 180332 KB Output is correct
10 Correct 115 ms 180332 KB Output is correct
11 Correct 116 ms 180332 KB Output is correct
12 Correct 113 ms 180332 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 180332 KB Output is correct
2 Correct 116 ms 180332 KB Output is correct
3 Correct 126 ms 180348 KB Output is correct
4 Correct 614 ms 188524 KB Output is correct
5 Correct 534 ms 188652 KB Output is correct
6 Correct 517 ms 185912 KB Output is correct
7 Correct 575 ms 185452 KB Output is correct
8 Correct 421 ms 186348 KB Output is correct
9 Correct 561 ms 185580 KB Output is correct
10 Correct 519 ms 185196 KB Output is correct
11 Correct 116 ms 180460 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 180460 KB Output is correct
2 Correct 114 ms 180332 KB Output is correct
3 Correct 116 ms 180332 KB Output is correct
4 Correct 115 ms 180332 KB Output is correct
5 Correct 115 ms 180460 KB Output is correct
6 Correct 118 ms 180332 KB Output is correct
7 Correct 116 ms 180332 KB Output is correct
8 Correct 115 ms 180460 KB Output is correct
9 Correct 116 ms 180332 KB Output is correct
10 Correct 116 ms 180516 KB Output is correct
11 Correct 115 ms 180332 KB Output is correct
12 Correct 974 ms 188604 KB Output is correct
13 Correct 1524 ms 185196 KB Output is correct
14 Correct 399 ms 185452 KB Output is correct
15 Correct 1776 ms 185452 KB Output is correct
16 Correct 332 ms 185324 KB Output is correct
17 Correct 777 ms 186312 KB Output is correct
18 Correct 1314 ms 186348 KB Output is correct
19 Correct 1097 ms 186556 KB Output is correct
20 Correct 1002 ms 185980 KB Output is correct
21 Correct 118 ms 180332 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 180332 KB Output is correct
2 Correct 117 ms 180332 KB Output is correct
3 Correct 116 ms 180332 KB Output is correct
4 Correct 114 ms 180508 KB Output is correct
5 Correct 114 ms 180332 KB Output is correct
6 Correct 117 ms 180372 KB Output is correct
7 Correct 114 ms 180332 KB Output is correct
8 Correct 115 ms 180332 KB Output is correct
9 Correct 117 ms 180460 KB Output is correct
10 Correct 114 ms 180332 KB Output is correct
11 Correct 114 ms 180332 KB Output is correct
12 Correct 608 ms 188652 KB Output is correct
13 Correct 530 ms 188940 KB Output is correct
14 Correct 526 ms 185708 KB Output is correct
15 Correct 565 ms 185500 KB Output is correct
16 Correct 423 ms 186348 KB Output is correct
17 Correct 554 ms 185580 KB Output is correct
18 Correct 520 ms 185276 KB Output is correct
19 Correct 963 ms 188780 KB Output is correct
20 Correct 1536 ms 185196 KB Output is correct
21 Correct 399 ms 185196 KB Output is correct
22 Correct 1778 ms 185416 KB Output is correct
23 Correct 324 ms 185324 KB Output is correct
24 Correct 786 ms 186220 KB Output is correct
25 Correct 1321 ms 186324 KB Output is correct
26 Correct 1129 ms 186612 KB Output is correct
27 Correct 1039 ms 185964 KB Output is correct
28 Runtime error 644 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 180332 KB Output is correct
2 Correct 117 ms 180460 KB Output is correct
3 Correct 114 ms 180332 KB Output is correct
4 Correct 115 ms 180332 KB Output is correct
5 Correct 114 ms 180332 KB Output is correct
6 Correct 114 ms 180332 KB Output is correct
7 Correct 118 ms 180332 KB Output is correct
8 Correct 116 ms 180332 KB Output is correct
9 Correct 116 ms 180332 KB Output is correct
10 Correct 116 ms 180332 KB Output is correct
11 Correct 115 ms 180332 KB Output is correct
12 Correct 613 ms 188624 KB Output is correct
13 Correct 526 ms 188780 KB Output is correct
14 Correct 534 ms 185964 KB Output is correct
15 Correct 563 ms 185836 KB Output is correct
16 Correct 425 ms 186476 KB Output is correct
17 Correct 559 ms 185580 KB Output is correct
18 Correct 520 ms 185196 KB Output is correct
19 Correct 964 ms 188812 KB Output is correct
20 Correct 1547 ms 185300 KB Output is correct
21 Correct 405 ms 185324 KB Output is correct
22 Correct 1797 ms 185324 KB Output is correct
23 Correct 328 ms 185324 KB Output is correct
24 Correct 777 ms 186228 KB Output is correct
25 Correct 1311 ms 186348 KB Output is correct
26 Correct 1111 ms 186612 KB Output is correct
27 Correct 1065 ms 186092 KB Output is correct
28 Runtime error 632 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -