oj.uz

Submission #852383

# Submission time Handle Problem Language Result Execution time Memory
852383 2023-09-21T17:18:02 Z jerzyk Seats (IOI18_seats) C++17
53 / 100
 1912 ms 110052 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 = 4, m, nm;
int drz[2 * N], il[2 * N], laz[2 * N];
vector<int> tab[N];
pair<int, int> 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)
{if(a <= b) Change(1, 0, N - 1, a, b, x);}

inline void HN(vector<vector<int>> v, int x)
{
    if(v[0][0] > v[1][1]) swap(v[0][0], v[1][1]);
    if(v[0][1] > v[1][0]) swap(v[0][1], v[1][0]);
    if(v[0][1] < v[0][0])
        {swap(v[0][0], v[0][1]); swap(v[1][0], v[1][1]);}
    //cout << "\n" << v[0][0] << " " << v[0][1] << "\n";
    //cout << v[1][0] << " " << v[1][1] << "\n";
    CH(v[0][0], min(v[0][1], v[1][1]) - 1, x);
    CH(min(v[1][1], v[1][0]), max(v[1][1], v[1][0]) - 1, x * 5);
}

inline void HLP(pair<int, int> a, int d)
{
    vector<int> x(2, 0); vector<vector<int>> v(2, x);
    for(int i = a.st - 1; i <= a.st; ++i)
        for(int j = a.nd - 1; j <= a.nd; ++j)
        {
            v[0][0] = tab[i][j]; v[0][1] = tab[i][j + 1]; v[1][0] = tab[i + 1][j]; v[1][1] = tab[i + 1][j + 1];
            HN(v, d);
        }
}

void Query(int a, int b)
{
    ++a; ++b;
    pair<int, int> x = wh[a], y = wh[b];
    HLP(x, -1); HLP(y, -1);
    swap(tab[x.st][x.nd], tab[y.st][y.nd]);
    wh[a] = y; wh[b] = x;
    HLP(x, 1); HLP(y, 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; vector<int> p1(m + 5, 0), p2(m + 5, nm + 10);
    p1[0] = nm + 10; p1[m + 1] = nm + 10; tab[0] = p2; tab[n + 1] = p2;
    for(int i = 1; i <= n; ++i) tab[i] = p1;
    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 <= nm; ++i)
    {
        tab[R[i - 1] + 1][C[i - 1] + 1] = i;
        wh[i] = make_pair(R[i - 1] + 1, C[i - 1] + 1);
    }
    vector<int> x(2, 0); vector<vector<int>> v(2, x);
    for(int i = 0; i <= n; ++i)
    {
        for(int j = 0; j <= m; ++j)
        {
            v[0][0] = tab[i][j]; v[0][1] = tab[i][j + 1]; v[1][0] = tab[i + 1][j]; v[1][1] = tab[i + 1][j + 1];
            HN(v, 1);
        }
    }
    //cout << "XD " << Ans() << "\n";
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 47452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 47452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1349 ms 93544 KB Output is correct
2 Correct 732 ms 93816 KB Output is correct
3 Correct 754 ms 93340 KB Output is correct
4 Correct 632 ms 93268 KB Output is correct
5 Correct 647 ms 93344 KB Output is correct
6 Correct 606 ms 93424 KB Output is correct
7 Correct 666 ms 93368 KB Output is correct
8 Correct 730 ms 93340 KB Output is correct
9 Correct 691 ms 93560 KB Output is correct
10 Correct 690 ms 93524 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 48012 KB Output is correct
2 Incorrect 131 ms 54932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1115 ms 49092 KB Output is correct
2 Correct 1061 ms 49100 KB Output is correct
3 Correct 746 ms 49808 KB Output is correct
4 Correct 438 ms 49124 KB Output is correct
5 Correct 389 ms 51888 KB Output is correct
6 Correct 1006 ms 108116 KB Output is correct
7 Correct 1168 ms 110000 KB Output is correct
8 Correct 989 ms 110052 KB Output is correct
9 Correct 1912 ms 109992 KB Output is correct
10 Correct 992 ms 109908 KB Output is correct
11 Correct 987 ms 109140 KB Output is correct
12 Correct 969 ms 108136 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 47452 KB Output isn't correct
2 Halted 0 ms 0 KB -