Submission #153076

#	Time	Username	Problem	Language	Result	Execution time	Memory
153076		arnold518	Seats (IOI18_seats)	C++14	100 / 100	3346 ms	135944 KiB

seats

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

int H, W, R[MAXN+10], C[MAXN+10];
vector<vector<int>> A;
int psum1[MAXN+10], psum2[MAXN+10];

pii val[4*MAXN+10], lazy[4*MAXN+10];
int cnt[4*MAXN+10];

void init(int node, int tl, int tr)
{
    if(tl==tr)
    {
        val[node]={psum1[tl], psum2[tl]};
        cnt[node]=1;
        return;
    }
    int mid=tl+tr>>1;
    init(node*2, tl, mid);
    init(node*2+1, mid+1, tr);
    if(val[node*2]==val[node*2+1]) val[node]=val[node*2], cnt[node]=cnt[node*2]+cnt[node*2+1];
    else if(val[node*2]<val[node*2+1]) val[node]=val[node*2], cnt[node]=cnt[node*2];
    else val[node]=val[node*2+1], cnt[node]=cnt[node*2+1];
}

void busy(int node, int tl, int tr)
{
    if(lazy[node]==pii(0, 0)) return;
    val[node].first+=lazy[node].first;
    val[node].second+=lazy[node].second;
    if(tl!=tr)
    {
        lazy[node*2].first+=lazy[node].first; lazy[node*2].second+=lazy[node].second;
        lazy[node*2+1].first+=lazy[node].first; lazy[node*2+1].second+=lazy[node].second;
    }
    lazy[node]=pii(0, 0);
}

void update(int node, int tl, int tr, int l, int r, int v, int t)
{
    busy(node, tl, tr);
    if(r<tl || tr<l) return;
    if(l<=tl && tr<=r)
    {
        if(t==1) lazy[node].first+=v;
        else lazy[node].second+=v;
        busy(node, tl, tr);
        return;
    }
    int mid=tl+tr>>1;
    update(node*2, tl, mid, l, r, v, t);
    update(node*2+1, mid+1, tr, l, r, v, t);
    if(val[node*2]==val[node*2+1]) val[node]=val[node*2], cnt[node]=cnt[node*2]+cnt[node*2+1];
    else if(val[node*2]<val[node*2+1]) val[node]=val[node*2], cnt[node]=cnt[node*2];
    else val[node]=val[node*2+1], cnt[node]=cnt[node*2+1];
}

int query()
{
    busy(1, 1, H*W);
    if(val[1]==pii(4, 0)) return cnt[1];
    else return 0;
}

void give_initial_chart(int _H, int _W, vector<int> _R, vector<int> _C)
{
    int i, j;
    H=_H; W=_W; A=vector<vector<int>>(H+2, vector<int>(W+2, H*W+1));
    for(i=0; i<H*W; i++) R[i+1]=_R[i]+1, C[i+1]=_C[i]+1;
    for(i=1; i<=H*W; i++) A[R[i]][C[i]]=i;

    for(i=0; i<=H; i++) for(j=0; j<=W; j++)
    {
        vector<int> V;
        V.push_back(A[i][j]);
        V.push_back(A[i+1][j]);
        V.push_back(A[i][j+1]);
        V.push_back(A[i+1][j+1]);
        sort(V.begin(), V.end());

        psum1[V[0]]++; psum1[V[1]]--;
        psum2[V[2]]++; psum2[V[3]]--;
    }
    for(i=1; i<=H*W; i++) psum1[i]+=psum1[i-1], psum2[i]+=psum2[i-1];
    init(1, 1, H*W);
}

void update(int y, int x, int val)
{
    vector<int> V;
    V.push_back(A[y][x]);
    V.push_back(A[y+1][x]);
    V.push_back(A[y][x+1]);
    V.push_back(A[y+1][x+1]);
    sort(V.begin(), V.end());

    update(1, 1, H*W, V[0], V[1]-1, val, 1);
    update(1, 1, H*W, V[2], V[3]-1, val, 2);
}

int swap_seats(int a, int b)
{
    int i, j;
    a++; b++;

    update(R[a]-1, C[a]-1, -1);
    update(R[a], C[a]-1, -1);
    update(R[a]-1, C[a], -1);
    update(R[a], C[a], -1);

    update(R[b]-1, C[b]-1, -1);
    update(R[b], C[b]-1, -1);
    update(R[b]-1, C[b], -1);
    update(R[b], C[b], -1);

    swap(R[a], R[b]); swap(C[a], C[b]); swap(A[R[a]][C[a]], A[R[b]][C[b]]);

    update(R[a]-1, C[a]-1, 1);
    update(R[a], C[a]-1, 1);
    update(R[a]-1, C[a], 1);
    update(R[a], C[a], 1);

    update(R[b]-1, C[b]-1, 1);
    update(R[b], C[b]-1, 1);
    update(R[b]-1, C[b], 1);
    update(R[b], C[b], 1);

    return query();
}

Compilation message (stderr)

seats.cpp: In function 'void init(int, int, int)':
seats.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
seats.cpp: In function 'void update(int, int, int, int, int, int, int)':
seats.cpp:58:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:111:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
seats.cpp:111:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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