oj.uz

답안 #903177

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
903177 2024-01-11T06:04:56 Z gaga999 자리 배치 (IOI18_seats) C++17
100 / 100
 2419 ms 188500 KB 
#include <cstdio>
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stdlib.h>
#include <cstring>
#include <string.h>
#include <string>
#include <sstream>
#include <assert.h>
#include <climits>
#include <sstream>
#include <numeric>
#include <time.h>
#include <limits.h>
#include <list>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <iomanip>
#include <complex>
#include <chrono>
#include <fstream>
#include <functional>
#include <unistd.h>
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt")
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define init(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
typedef complex<double> cd;
// const int M = 998244353;

// random_device rm;
// mt19937 rg(rm());
// default_random_engine rg(rm());
// uniform_int_distribution<int> rd(INT_MIN, INT_MAX);
// uniform_real_distribution<double> rd(0, M_PI);

void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }

inline char gc()
{
    const static int SZ = 1 << 16;
    static char buf[SZ], *p1, *p2;
    if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2))
        return -1;
    return *p1++;
}
void rd() {}
template <typename T, typename... U>
void rd(T &x, U &...y)
{
    x = 0;
    bool f = 0;
    char c = gc();
    while (!isdigit(c))
        f ^= !(c ^ 45), c = gc();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
    f && (x = -x), rd(y...);
}

template <typename T>
void prt(T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        prt(x / 10);
    putchar((x % 10) ^ 48);
}
const int N = 1e6 + 6;
vector<int> xr, yr;
vector<vector<int>> gd;
struct TR
{
    llt vl, tg;
    int num = 1;
    inline void add(llt x) { vl += x, tg += x; }
} tr[N << 2];
int ql, qr, vv, L, R, RT;
void cg(int l = L, int r = R, int id = RT)
{
    if (ql > qr)
        return;
    if (ql <= l && r <= qr)
    {
        tr[id].add(vv);
        return;
    }
    if (tr[id].tg)
    {
        tr[ls(id)].add(tr[id].tg);
        tr[rs(id)].add(tr[id].tg);
        tr[id].tg = 0;
    }
    int m = (l + r) >> 1;
    if (ql <= m)
        cg(l, m, ls(id));
    if (qr > m)
        cg(m + 1, r, rs(id));
    tr[id].vl = min(tr[ls(id)].vl, tr[rs(id)].vl);
    tr[id].num = 0;
    if (tr[ls(id)].vl == tr[id].vl)
        tr[id].num += tr[ls(id)].num;
    if (tr[rs(id)].vl == tr[id].vl)
        tr[id].num += tr[rs(id)].num;
}

inline void mod(int x, int y, int bl)
{
    int tp[4] = {gd[x][y], gd[x + 1][y + 1], gd[x][y + 1], gd[x + 1][y]};
    sort(tp, tp + 4);
    ql = tp[0], qr = tp[1] - 1, vv = bl, cg();
    ql = tp[2], qr = tp[3] - 1, vv = INF * bl, cg();
}

inline void slv(int x, int y, int bl)
{
    mod(x, y, bl);
    mod(x - 1, y - 1, bl);
    mod(x, y - 1, bl);
    mod(x - 1, y, bl);
}

int swap_seats(int l, int r)
{
    slv(xr[l], yr[l], -1);
    slv(xr[r], yr[r], -1);
    swap(gd[xr[l]][yr[l]], gd[xr[r]][yr[r]]);
    swap(xr[l], xr[r]), swap(yr[l], yr[r]);
    slv(xr[l], yr[l], 1);
    slv(xr[r], yr[r], 1);
    return tr[RT].num;
}

void give_initial_chart(int H, int W, vector<int> X, vector<int> Y)
{
    gd = vector<vector<int>>(H + 2, vector<int>(W + 2, INF));
    int A = H * W;
    xr = X, yr = Y;
    for (int i = 0; i < A; i++)
        gd[++xr[i]][++yr[i]] = i;
    L = 0, R = A - 1, RT = 1;
    for (int i = 0; i <= H; i++)
        for (int j = 0; j <= W; j++)
            mod(i, j, 1);
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 94520 KB Output is correct
2 Correct 26 ms 94300 KB Output is correct
3 Correct 40 ms 94504 KB Output is correct
4 Correct 29 ms 94376 KB Output is correct
5 Correct 24 ms 94300 KB Output is correct
6 Correct 35 ms 94488 KB Output is correct
7 Correct 37 ms 94464 KB Output is correct
8 Correct 32 ms 94504 KB Output is correct
9 Correct 30 ms 94296 KB Output is correct
10 Correct 34 ms 94480 KB Output is correct
11 Correct 36 ms 94312 KB Output is correct
12 Correct 23 ms 94304 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 94520 KB Output is correct
2 Correct 26 ms 94300 KB Output is correct
3 Correct 40 ms 94504 KB Output is correct
4 Correct 29 ms 94376 KB Output is correct
5 Correct 24 ms 94300 KB Output is correct
6 Correct 35 ms 94488 KB Output is correct
7 Correct 37 ms 94464 KB Output is correct
8 Correct 32 ms 94504 KB Output is correct
9 Correct 30 ms 94296 KB Output is correct
10 Correct 34 ms 94480 KB Output is correct
11 Correct 36 ms 94312 KB Output is correct
12 Correct 23 ms 94304 KB Output is correct
13 Correct 66 ms 94896 KB Output is correct
14 Correct 74 ms 94824 KB Output is correct
15 Correct 54 ms 94824 KB Output is correct
16 Correct 41 ms 95336 KB Output is correct
17 Correct 68 ms 94828 KB Output is correct
18 Correct 60 ms 94852 KB Output is correct
19 Correct 61 ms 94816 KB Output is correct
20 Correct 43 ms 95096 KB Output is correct
21 Correct 38 ms 94808 KB Output is correct
22 Correct 38 ms 95324 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1607 ms 137808 KB Output is correct
2 Correct 804 ms 137676 KB Output is correct
3 Correct 803 ms 137632 KB Output is correct
4 Correct 681 ms 137640 KB Output is correct
5 Correct 721 ms 137752 KB Output is correct
6 Correct 736 ms 137804 KB Output is correct
7 Correct 706 ms 137808 KB Output is correct
8 Correct 716 ms 137800 KB Output is correct
9 Correct 746 ms 137804 KB Output is correct
10 Correct 672 ms 137756 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 94848 KB Output is correct
2 Correct 127 ms 98132 KB Output is correct
3 Correct 717 ms 137800 KB Output is correct
4 Correct 1592 ms 138036 KB Output is correct
5 Correct 599 ms 145644 KB Output is correct
6 Correct 1546 ms 188500 KB Output is correct
7 Correct 663 ms 140380 KB Output is correct
8 Correct 870 ms 137880 KB Output is correct
9 Correct 661 ms 138008 KB Output is correct
10 Correct 678 ms 142448 KB Output is correct
11 Correct 627 ms 161360 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 96028 KB Output is correct
2 Correct 87 ms 96200 KB Output is correct
3 Correct 152 ms 95924 KB Output is correct
4 Correct 182 ms 95952 KB Output is correct
5 Correct 293 ms 96472 KB Output is correct
6 Correct 1092 ms 146648 KB Output is correct
7 Correct 1201 ms 146552 KB Output is correct
8 Correct 932 ms 146604 KB Output is correct
9 Correct 2212 ms 146548 KB Output is correct
10 Correct 930 ms 146424 KB Output is correct
11 Correct 971 ms 146548 KB Output is correct
12 Correct 852 ms 146772 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 94520 KB Output is correct
2 Correct 26 ms 94300 KB Output is correct
3 Correct 40 ms 94504 KB Output is correct
4 Correct 29 ms 94376 KB Output is correct
5 Correct 24 ms 94300 KB Output is correct
6 Correct 35 ms 94488 KB Output is correct
7 Correct 37 ms 94464 KB Output is correct
8 Correct 32 ms 94504 KB Output is correct
9 Correct 30 ms 94296 KB Output is correct
10 Correct 34 ms 94480 KB Output is correct
11 Correct 36 ms 94312 KB Output is correct
12 Correct 23 ms 94304 KB Output is correct
13 Correct 66 ms 94896 KB Output is correct
14 Correct 74 ms 94824 KB Output is correct
15 Correct 54 ms 94824 KB Output is correct
16 Correct 41 ms 95336 KB Output is correct
17 Correct 68 ms 94828 KB Output is correct
18 Correct 60 ms 94852 KB Output is correct
19 Correct 61 ms 94816 KB Output is correct
20 Correct 43 ms 95096 KB Output is correct
21 Correct 38 ms 94808 KB Output is correct
22 Correct 38 ms 95324 KB Output is correct
23 Correct 1607 ms 137808 KB Output is correct
24 Correct 804 ms 137676 KB Output is correct
25 Correct 803 ms 137632 KB Output is correct
26 Correct 681 ms 137640 KB Output is correct
27 Correct 721 ms 137752 KB Output is correct
28 Correct 736 ms 137804 KB Output is correct
29 Correct 706 ms 137808 KB Output is correct
30 Correct 716 ms 137800 KB Output is correct
31 Correct 746 ms 137804 KB Output is correct
32 Correct 672 ms 137756 KB Output is correct
33 Correct 66 ms 94848 KB Output is correct
34 Correct 127 ms 98132 KB Output is correct
35 Correct 717 ms 137800 KB Output is correct
36 Correct 1592 ms 138036 KB Output is correct
37 Correct 599 ms 145644 KB Output is correct
38 Correct 1546 ms 188500 KB Output is correct
39 Correct 663 ms 140380 KB Output is correct
40 Correct 870 ms 137880 KB Output is correct
41 Correct 661 ms 138008 KB Output is correct
42 Correct 678 ms 142448 KB Output is correct
43 Correct 627 ms 161360 KB Output is correct
44 Correct 57 ms 96028 KB Output is correct
45 Correct 87 ms 96200 KB Output is correct
46 Correct 152 ms 95924 KB Output is correct
47 Correct 182 ms 95952 KB Output is correct
48 Correct 293 ms 96472 KB Output is correct
49 Correct 1092 ms 146648 KB Output is correct
50 Correct 1201 ms 146552 KB Output is correct
51 Correct 932 ms 146604 KB Output is correct
52 Correct 2212 ms 146548 KB Output is correct
53 Correct 930 ms 146424 KB Output is correct
54 Correct 971 ms 146548 KB Output is correct
55 Correct 852 ms 146772 KB Output is correct
56 Correct 112 ms 95956 KB Output is correct
57 Correct 250 ms 95992 KB Output is correct
58 Correct 402 ms 96320 KB Output is correct
59 Correct 1306 ms 138924 KB Output is correct
60 Correct 2365 ms 138760 KB Output is correct
61 Correct 1218 ms 138764 KB Output is correct
62 Correct 957 ms 142636 KB Output is correct
63 Correct 2419 ms 141340 KB Output is correct
64 Correct 1524 ms 139668 KB Output is correct
65 Correct 1300 ms 138996 KB Output is correct
66 Correct 1386 ms 139112 KB Output is correct
67 Correct 1440 ms 143516 KB Output is correct
68 Correct 1053 ms 153112 KB Output is correct
69 Correct 2189 ms 162080 KB Output is correct