Submission #1186455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186455		Tymond	Seats (IOI18_seats)	C++20	100 / 100	2777 ms	133976 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

const int INF = 1e9;
const int MAXN =  1e6 + 7;
vector<pii> pos;
vector<vi> A;
int h, w;

struct Node{
    int val1 = 0, val2 = 0, cnt = 1;
    Node(){}
    Node(int x, int y, int z) : val1(x), val2(y), cnt(z){}

    Node operator+(const Node &other) const{
        if(val1 == other.val1 && val2 == other.val2){
            return Node(val1, val2, cnt+other.cnt);
        }
        if(val1 == other.val1){
            return val2 < other.val2 ? *this : other;
        } 
        return val1 < other.val1 ? *this : other;
    }

    bool operator==(const Node &other) const{
        return val1 == other.val1 && val2 == other.val2;
    }
};

Node tree[4 * MAXN + 7];
int lazy1[4 * MAXN + 7];
int lazy2[4 * MAXN + 7];

void Push(int v){
    if(lazy1[v]){
        tree[2 * v].val1 += lazy1[v];
        tree[2 * v + 1].val1 += lazy1[v];
        lazy1[2 * v] += lazy1[v];
        lazy1[2 * v + 1] += lazy1[v];
        lazy1[v] = 0;
    }

    if(lazy2[v]){
        tree[2 * v].val2 += lazy2[v];
        tree[2 * v + 1].val2 += lazy2[v];
        lazy2[2 * v] += lazy2[v];
        lazy2[2 * v + 1] += lazy2[v];
        lazy2[v] = 0;
    }
}

void upd1(int v, int l, int p, int a, int b, int val){
    if(p < a || b < l){
        return;
    }

    if(a <= l && p <= b){
        tree[v].val1 += val;
        lazy1[v] += val;
        return;
    }
    int mid = (l + p) / 2;
    Push(v);
    upd1(2 * v, l, mid, a, b, val);
    upd1(2 * v + 1, mid + 1, p, a, b, val);
    tree[v] = tree[2 * v] + tree[2 * v + 1]; 
}

void upd2(int v, int l, int p, int a, int b, int val){
    if(p < a || b < l){
        return;
    }

    if(a <= l && p <= b){
        tree[v].val2 += val;
        lazy2[v] += val;
        return;
    }
    int mid = (l + p) / 2;
    Push(v);
    upd2(2 * v, l, mid, a, b, val);
    upd2(2 * v + 1, mid + 1, p, a, b, val);
    tree[v] = tree[2 * v] + tree[2 * v + 1]; 
}

void change1(int x, int y, int val){
    vi curr = {A[x][y], A[x + 1][y], A[x][y + 1], A[x + 1][y + 1]};
    sort(all(curr));
    upd1(1, 0, h * w - 1, curr[0], curr[1] - 1, val);
}

void change2(int x, int y, int val){
    vi curr = {A[x][y], A[x + 1][y], A[x][y + 1], A[x + 1][y + 1]};
    sort(all(curr));
    upd2(1, 0, h * w - 1, curr[2], curr[3] - 1, val);
}

void give_initial_chart(int H, int W, vi R, vi C){
    h = H;
    w = W;
    pos.resize(h * w);
    A.resize(h + 2, vi(w + 2, h * w));
    for(int i = 0; i < h * w; i++){
        pos[i] = mp(R[i] + 1, C[i] + 1);
        A[R[i] + 1][C[i] + 1] = i;
    }
    for(int i = 0; i <= h; i++){
        for(int j = 0; j <= w; j++){
            change1(i, j, 1);
            change2(i, j, 1);
        }
    }
}

//zamień miejsca liczb a i b
//potem zwróć wynik po zamianie
int swap_seats(int a, int b) {
    int p[2] = {a, b};
    vector<pii> vec;
    for(int j = 0; j < 2; j++){
        for(int x = pos[p[j]].fi - 1; x <= pos[p[j]].fi; x++){
            for(int y = pos[p[j]].se - 1; y <= pos[p[j]].se; y++){
                vec.pb(mp(x,y));
            }
        }
    }
    sort(all(vec));
    vec.erase(unique(all(vec)), vec.end());
    for(auto [x, y] : vec){
        change1(x, y, -1);
        change2(x, y, -1);
    }
    swap(pos[p[0]], pos[p[1]]);
    swap(A[pos[p[0]].fi][pos[p[0]].se], A[pos[p[1]].fi][pos[p[1]].se]);
    for(auto [x, y] : vec){
        change1(x, y, 1);
        change2(x, y, 1);
    }
    
    return tree[1].cnt;
}

/*int main(){
    give_initial_chart(2, 3, {0, 1, 1, 0, 0, 1}, {0, 0, 1, 1, 2, 2});
    
    cout << swap_seats(0, 5) << '\n';
    cout << swap_seats(0, 5) << '\n';

    return 0;
}*/

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 6 / 6
• Subtask 5: 33 / 33
• Subtask 6: 30 / 30