Submission #80230

#	Time	Username	Problem	Language	Result	Execution time	Memory
80230		Nazik_number_one	자리 배치 (IOI18_seats)	C++14	70 / 100	4099 ms	131912 KiB

seats

#include "seats.h"

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct node{
    int s, k, ob;
    node(){
        s = 1e9;
        k = ob = 0;
    }
    node (node a, node b){
        s = min(a.s, b.s);
        k = ob = 0;
        if (a.s == s)k += a.k;
        if (b.s == s)k += b.k;
    }
};
vector < vector < int > > aa;
int n, m, t, sz;
pair < int, int > p[N];
node tree[N * 4];

inline node mrg(node a, node b){
    node c;
    c.s = min(a.s, b.s);
    c.k = c.ob = 0;
    if (a.s == c.s)c.k += a.k;
    if (b.s == c.s)c.k += b.k;
    return c;
}

inline void push(int v, int l, int r){
    if (tree[v].ob == 0)return;
    tree[v].s += tree[v].ob;
    if (l != r){
        tree[v + v].ob += tree[v].ob;
        tree[v + v + 1].ob += tree[v].ob;
    }
    tree[v].ob = 0;
}

inline void add(int v, int l, int r, int ll, int rr, int x){
    push(v, l, r);
    if (l > r || ll > rr || l > rr || r < ll)return;
    if (l >= ll && r <= rr){
        tree[v].ob = x;
        push(v, l, r);
        return;
    }
    int mid = (l + r) / 2;
    add(v + v, l, mid, ll, rr, x);
    add(v + v + 1, mid + 1, r, ll, rr, x);
    tree[v] = mrg(tree[v + v], tree[v + v + 1]);
}

inline node get(int v, int l, int r, int ll, int rr){
    push(v, l, r);
    if (l > r || ll > rr || l > rr || r < ll)return node();
    if (l >= ll && r <= rr)return tree[v];
    int mid = (l + r) / 2;
    node x = get(v + v, l, mid, ll, rr), y = get(v + v + 1, mid + 1, r, ll, rr);
    tree[v] = mrg(tree[v + v], tree[v + v + 1]);
    return mrg(x, y);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H, m = W;
    t = n * m;
    sz = 1;
    while (sz < t){
        sz *= 2;
    }
    for (int i = sz; i <= sz + t - 1; ++i){
        tree[i].k = 1;
        tree[i].s = 0;
    }
    for (int i = sz - 1; i > 0; --i){
        tree[i].s = 0;
        tree[i].k = tree[i + i].k + tree[i + i + 1].k;
    }
    aa.resize(n + 2);
    aa[0].resize(m + 2, t);
    for (int i = 1; i <= n; ++i){
        aa[i].resize(m + 2);
        aa[i][0] = t;
        aa[i][m + 1] = t;
    }
    aa[n + 1].resize(m + 2, t);
    for (int i = 0; i < t; ++i){
        aa[R[i] + 1][C[i] + 1] = i;
        p[i + 1] = make_pair(R[i] + 1, C[i] + 1);
    }
    vector < int > b;
    b.resize(4);
    for (int i = 1; i <= n + 1; ++i){
        for (int j = 1; j <= m + 1; ++j){
            b[0] = aa[i - 1][j - 1], b[1] = aa[i][j - 1], b[2] = aa[i - 1][j], b[3] = aa[i][j];
            sort(b.begin(), b.end());
            add(1, sz, sz + sz - 1, sz + b[0], sz + b[1] - 1, 1);
            add(1, sz, sz + sz - 1, sz + b[2], sz + b[3] - 1, 1);
        }
    }
}

int swap_seats(int a, int b) {
    a++;
    b++;
    //cout <<a<<" "<<b<<" "<<" "<<p[a].first<<" "<<p[a].second<<" "<<p[b].first<<" "<<p[b].second<<endl;
    vector < pair < int, int > > c;
    c.push_back(make_pair(p[a].first, p[a].second));
    c.push_back(make_pair(p[a].first + 1, p[a].second));
    c.push_back(make_pair(p[a].first, p[a].second + 1));
    c.push_back(make_pair(p[a].first + 1, p[a].second + 1));
    c.push_back(make_pair(p[b].first, p[b].second));
    c.push_back(make_pair(p[b].first + 1, p[b].second));
    c.push_back(make_pair(p[b].first, p[b].second + 1));
    c.push_back(make_pair(p[b].first + 1, p[b].second + 1));
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    vector < int > bb;
    bb.resize(4);
    for (int e = 0; e < c.size(); ++e){
        int i = c[e].first, j = c[e].second;
        bb[0] = aa[i - 1][j - 1], bb[1] = aa[i][j - 1], bb[2] = aa[i - 1][j], bb[3] = aa[i][j];
        sort(bb.begin(), bb.end());
        add(1, sz, sz + sz - 1, sz + bb[0], sz + bb[1] - 1, -1);
        add(1, sz, sz + sz - 1, sz + bb[2], sz + bb[3] - 1, -1);
    }
    //return 0;
    swap(aa[p[a].first][p[a].second], aa[p[b].first][p[b].second]);
    swap(p[a], p[b]);
    for (int e = 0; e < c.size(); ++e){
        int i = c[e].first, j = c[e].second;
        bb[0] = aa[i - 1][j - 1], bb[1] = aa[i][j - 1], bb[2] = aa[i - 1][j], bb[3] = aa[i][j];
        sort(bb.begin(), bb.end());
        add(1, sz, sz + sz - 1, sz + bb[0], sz + bb[1] - 1, 1);
        add(1, sz, sz + sz - 1, sz + bb[2], sz + bb[3] - 1, 1);
    }
    node v = get(1, sz, sz + sz - 1, sz, sz + t - 1);
    //cout <<v.s<<" "<<v.k<<endl;
    if (v.s == 4)return v.k;else return 0;
}

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:123:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int e = 0; e < c.size(); ++e){
                     ~~^~~~~~~~~~
seats.cpp:133:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int e = 0; e < c.size(); ++e){
                     ~~^~~~~~~~~~

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