제출 #792889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
792889		fatemetmhr	Seats (IOI18_seats)	C++17	31 / 100	4094 ms	241680 KiB

seats

// Be name khode //


#include "seats.h"
#include <bits/stdc++.h>
 
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

 
#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair
 
typedef long long ll;
 
const int maxn = 1e6 + 10;
const int lg    = 20;

std::vector<int> r;

int n, m;
pair <ll, ll> a[maxn];
pair<int, pair<int, ll>> av[maxn];
set <int> avR[maxn], avC[maxn];
int mnR[maxn], mnC[maxn];

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H;
    m = W;
    for(int i = 0; i < n * m; i++){
        a[i] = {R[i], C[i]};
        avR[a[i].fi].insert(i);
        avC[a[i].se].insert(i);
    }
    fill(mnR, mnR + n + 5, n * m + 2);
    fill(mnC, mnC + m + 5, n * m + 2);
    for(int i = 0; i < n; i++) if(avR[i].size())
        mnR[i] = *avR[i].begin();
    for(int i = 0; i < m; i++) if(avC[i].size())
        mnC[i] = *avC[i].begin();
}

void add(int id){
    avR[a[id].fi].insert(id);
    avC[a[id].se].insert(id);
    mnR[a[id].fi] = min(mnR[a[id].fi], id);
    mnC[a[id].se] = min(mnC[a[id].se], id);
}

void remo(int id){
    avR[a[id].fi].erase(id);
    avC[a[id].se].erase(id);
    mnR[a[id].fi] = mnC[a[id].se] = n * m + 2;
    if(avR[a[id].fi].size())
        mnR[a[id].fi] = *avR[a[id].fi].begin();
    if(avC[a[id].se].size())
        mnC[a[id].se] = *avC[a[id].se].begin();
}

int swap_seats(int x, int y) {
    if(true && n * m > 10000){
        int ans = 0;
        remo(x);
        remo(y);
        swap(a[x], a[y]);
        add(x);
        add(y);
        int pt = 0;
        for(int i = 0; i < n; i++) if(mnR[i] < n * m)
            av[pt++] = {mnR[i], {0, i}};
        for(int i = 0; i < m; i++) if(mnC[i] < n * m)
            av[pt++] = {mnC[i], {1, i}};
        sort(av, av + pt);
        pair <ll, ll> h, w;
        h = {-1, maxn};
        w = h;
        int last = -1;
        //cout << av[0].fi << ' ' << av[0].se.fi << ' ' << av[0].se.se << endl;
        //cout << av[1].fi << ' ' << av[1].se.fi << ' ' << av[1].se.se << endl;
        for(int i = 0; i < pt; i++){
            ll k = (h.fi - h.se + 1) * (w.fi - w.se + 1);
            if(last > -1 && k >= last + 1 && k < av[i].fi + 1)
                ans++;
            /*
            if(i == 2){
                cout << "ha? " << h.fi << ' ' << h.se << ' ' << w.fi << ' ' << w.se << ' ' << k << ' ' << last << ' ' << av[i].fi << ' ' << ans << endl;
                cout << pt << ' ' << (last > -1) << ' ' <<  (k >= last) << ' ' <<  (k < av[i].fi) << ' ' << k << ' ' << av[i].fi << endl;
            }
            */
            if(av[i].se.fi){
                w.fi = max(w.fi, av[i].se.se);
                w.se = min(w.se, av[i].se.se);
            }
            else{
                h.fi = max(h.fi, av[i].se.se);
                h.se = min(h.se, av[i].se.se);
            }
            last = av[i].fi;
        }
        //cout << ans << endl;
        int k = (h.fi - h.se + 1) * (w.fi - w.se + 1);
        if(k >= last + 1)
            ans++;
        //cout << last << ' ' << k << endl;
        return ans;
    }
    swap(a[x], a[y]);
    pair <ll, ll> h, w;
    h = {a[0].fi, a[0].fi};
    w = {a[0].se, a[0].se};
    int ans = 0;
    for(int i = 0; i < n * m; i++){
        h.fi = max(h.fi, a[i].fi);
        h.se = min(h.se, a[i].fi);
        w.fi = max(w.fi, a[i].se);
        w.se = min(w.se, a[i].se);

        if((h.fi - h.se + 1) * (w.fi - w.se + 1) == i + 1)
            ans++;
    }
    return ans;
}

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