Submission #294168

#	Time	Username	Problem	Language	Result	Execution time	Memory
294168		shayan_p	Seats (IOI18_seats)	C++17	33 / 100	1496 ms	69624 KiB

seats

#include<bits/stdc++.h>
#include "seats.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

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

const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;


vector<int> X, Y;
int N, M;
/*
int solve(){
    int mnx = X[0], mxx = X[0];
    int mny = Y[0], mxy = Y[0];
    int ans = 1;
    for(int i = 1; i < N * M; i++){
	mnx = min(mnx, X[i]);
	mny = min(mny, Y[i]);
	mxx = max(mxx, X[i]);
	mxy = max(mxy, Y[i]);
	ans+= i+1 == (mxx - mnx + 1) * (mxy - mny + 1);
    }
    return ans;
    } */

int val[maxn];

int mx[4 * maxn], cnt[4 * maxn], lz[4 * maxn];

void mrg(int id){
    mx[id] = max(mx[2*id], mx[2*id+1]);
    cnt[id] = 0;
    if(mx[id] == mx[2*id])
	cnt[id]+= cnt[2*id];
    if(mx[id] == mx[2*id+1])
	cnt[id]+= cnt[2*id+1];
}
void build(int l = 0, int r = M, int id = 1){
    mx[id] = -l;
    cnt[id] = 1;
    if(r-l == 1)
	return;
    int mid = (l+r) >> 1;
    build(l, mid, 2*id);
    build(mid, r, 2*id+1);
}
void shift(int l, int r, int id = 1){
    mx[id]+= lz[id];
    if(r-l > 1)
	lz[2*id]+= lz[id], lz[2*id+1]+= lz[id];
    lz[id] = 0;
}
void add(int pos, int x, int l = 0, int r = M, int id = 1){
    shift(l, r, id);
    if(r <= pos)
	return;
    if(pos <= l){
	lz[id] = x;
	shift(l, r, id);
	return;
    }
    int mid = (l+r) >> 1;
    add(pos, x, l, mid, 2*id);
    add(pos, x, mid, r, 2*id+1);
    mrg(id);
}
void give_initial_chart(int N, int M, vector<int> X, vector<int> Y){
    ::N = N, ::M = M, ::X = X, ::Y = Y;
    assert(N == 1);
    for(int i = 0; i < M; i++)
	val[Y[i]] = i;
    build();
    for(int i = 0; i < M-1; i++)
	add(max(val[i], val[i+1]), 1);
}
int swap_seats(int a, int b){
    swap(Y[a], Y[b]);
    a = Y[a], b = Y[b];
    if(a > 0)
	add(max(val[a], val[a-1]), -1);
    if(a < M-1)
	add(max(val[a], val[a+1]), -1);
    if(b > 0)
	add(max(val[b], val[b-1]), -1);
    if(b < M-1)
	add(max(val[b], val[b+1]), -1);    
    swap(val[a], val[b]);
    if(a > 0)
	add(max(val[a], val[a-1]), 1);
    if(a < M-1)
	add(max(val[a], val[a+1]), 1);
    if(b > 0)
	add(max(val[b], val[b-1]), 1);
    if(b < M-1)
	add(max(val[b], val[b+1]), 1);
    return mx[1] == 0 ? cnt[1] : 0;
}

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