oj.uz

답안 #852093

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
852093 2023-09-21T08:24:33 Z jerzyk 자리 배치 (IOI18_seats) C++17
33 / 100
 1002 ms 65872 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "seats.h"

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<20;
int n, val = 2, m, nm;
int tab[N], drz[2 * N], il[2 * N], laz[2 * N], wh[N];

void Change(int v, int p, int k, int pz, int kz, int x)
{
    if(p > kz || k < pz) return;
    if(p >= pz && k <= kz)
    {
        drz[v] += x; laz[v] += x;
        return;
    }
    int m = (p + k) / 2;
    Change(v * 2, p, m, pz, kz, x);
    Change(v * 2 + 1, m + 1, k, pz, kz, x);
    drz[v] = min(drz[v * 2], drz[v * 2 + 1]); il[v] = 0;
    if(drz[v] == drz[v * 2]) il[v] += il[v * 2];
    if(drz[v] == drz[v * 2 + 1]) il[v] += il[v * 2 + 1];
    drz[v] += laz[v];
}

inline void CH(int a, int b, int x)
{Change(1, 0, N - 1, a, b, x);}

inline void HN(int a, int b, int x)
{
    if(b < a) swap(a, b);
    CH(a, b - 1, x);
}

inline void U(int v, int x)
{
    HN(tab[v - 1], tab[v], x);
    HN(tab[v], tab[v + 1], x);
}

void Query(int a, int b)
{
    ++a; ++b; a = wh[a]; b = wh[b];
    U(a, -1); U(b, -1);
    swap(tab[a], tab[b]);
    wh[tab[a]] = a; wh[tab[b]] = b;
    U(a, 1); U(b, 1);
}

int Ans()
{
    int ans = 0;
    if(drz[1] == val) ans += il[1];
    return ans;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) 
{
    n = H; m = W; nm = n * m;
    for(int i = N; i < 2 * N; ++i) il[i] = 1;
    drz[N] = N; for(int i = N + nm + 1; i < 2 * N; ++i) drz[i] = N;
    for(int v = N - 1; v > 0; --v)
    {
        drz[v] = min(drz[v * 2], drz[v * 2 + 1]);
        if(drz[v] == drz[v * 2]) il[v] += il[v * 2];
        if(drz[v] == drz[v * 2 + 1]) il[v] += il[v * 2 + 1];
    }
    for(int i = 1; i <= m; ++i)
    {
        tab[C[i - 1] + 1] = i;
        wh[i] = C[i - 1] + 1;
    }
    tab[0] = nm + 10; tab[m + 1] = nm + 10;
    for(int i = 1; i <= m + 1; ++i)
        HN(tab[i], tab[i - 1], 1);
    //cout << "XD " << drz[1] << " " << Ans() << "\n";
}

int swap_seats(int a, int b) 
{
    Query(a, b);
    return Ans();
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 23128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 23128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 177 ms 52532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 21404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 533 ms 22620 KB Output is correct
2 Correct 482 ms 22592 KB Output is correct
3 Correct 298 ms 22660 KB Output is correct
4 Correct 171 ms 22648 KB Output is correct
5 Correct 180 ms 24904 KB Output is correct
6 Correct 519 ms 63660 KB Output is correct
7 Correct 628 ms 65584 KB Output is correct
8 Correct 516 ms 65860 KB Output is correct
9 Correct 1002 ms 65600 KB Output is correct
10 Correct 509 ms 65872 KB Output is correct
11 Correct 499 ms 64596 KB Output is correct
12 Correct 518 ms 63420 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 23128 KB Output isn't correct
2 Halted 0 ms 0 KB -