| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 328572 | figter001 | Seats (IOI18_seats) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
vector<int> at,loc,d;
struct node{
node *l,*r;
int lazy,mn,cnt;
node(){
l = r = NULL;
mn = 1e9;
lazy = 0;
cnt = 1;
}
void pro(){
mn += lazy;
if(l != NULL)l->lazy += lazy;
if(r != NULL)r->lazy += lazy;
lazy = 0;
}
void marge(){
if(l->mn < r->mn){
mn = l->mn;
cnt = l->cnt;
}else if(r->mn < l->mn){
mn = r->mn;
cnt = r->cnt;
}else if(l->mn == r->mn){
mn = l->mn;
cnt = l->cnt + r->cnt;
}
}
};
int n;
node *head;
void update(int at,int val,node *&n = head,int s = 1,int e = ::n){
if(n == NULL)n = new node();
if(s > at || e < at)return;
if(s == e){
n->mn = val;
n->cnt = 1;
return;
}
update(at , val , n->l , s , (s+e)/2);
update(at , val , n->r , (s+e)/2+1 , e);
n->marge();
// cerr << ' ' << s << ' ' << e << ' ' << n->mn << ' ' << n->cnt << ' ' << val << '\n';
}
void update_range(int l,int r,int val,node *&n = head,int s = 1,int e = ::n){
n->pro();
if(s > r || e < l || l > r)return;
if(s >= l && e <= r){
n->lazy += val;
n->pro();
return;
}
update_range(l , r , val , n->l , s , (s+e)/2);
update_range(l , r , val , n->r , (s+e)/2+1 , e);
n->marge();
// cerr << ' ' << s << ' ' << e << ' ' << n->mn << ' ' << n->cnt << ' ' << val << '\n';
}
pair<int,int> get(int l,int r,node *& n = head,int s = 1,int e = TO){
n->pro();
if(n == NULL)return {1e9,0};
if(s > r || e < l || l > r)return {1e9,0};
if(s >= l && e <= r)return {n->mn,n->cnt};
pair<int,int> a = get(l , r , n->l , s , (s+e) / 2);
pair<int,int> b = get(l , r , n->r , (s+e)/2+1 , e);
if(a.first < b.first)return a;
else if(a.first > b.first)return b;
else{
return {a.first , a.second + b.second};
}
}
int getd(int i,int x){
if(i < 0 || i >= (int)loc.size() || loc[i] > x)return 1;
return -1;
}
void add(int l,int r,int v){
update_range(l,r,v);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H*W;
at = loc = d = vector<int> (n);
head = new node();
for(int i=0;i<n;i++){
at[i] = C[i];
loc[C[i]] = i;
}
int sum = 0;
for(int i=0;i<n;i++){
d[i] = getd(at[i]-1,i) + getd(at[i]+1,i);
sum += d[i];
// cerr << sum << '-' << d[i] << ' ';
update(i + 1 , sum);
}
// cerr << head->mn << ' ' << head->cnt << '\n';
// cerr << '\n';
return;
}
int swap_seats(int a, int b) {
int len = loc.size();
swap(at[a] , at[b]);
swap(loc[at[a]] , loc[at[b]]);
int A = a,B = b;
// cerr << "MN : " << get(1,len).first << ' ' << get(1,len).second << '\n';
for(int i=-1;i<=1;i++){
// cerr << a << ' ' << b << '\n';
if(at[A]+i >= 0 && at[A]+i < loc.size()){
int a = loc[at[A]+i];
// cerr << "A : " << a << '\n';
// cerr << d[a] << ' ';
add(a+1 , len , -d[a]);
d[a] = getd(at[a] - 1 , a) + getd(at[a] + 1 , a);
// cerr << d[a] << '\n';
add(a+1 , len , d[a]);
}
if(at[B]+i >= 0 && at[B]+i < loc.size()){
int b = loc[at[B]+i];
// cerr << "B : " << b << '\n';
// cerr << d[b] << ' ';
add(b+1 , len , -d[b]);
d[b] = getd(at[b] - 1 , b) + getd(at[b] + 1 , b);
// cerr << d[b] << '\n';
add(b+1 , len , d[b]);
}
// cerr << "WTF : " << get(1,len-1).first << ' ' << get(1,len-1).second << '\n';
// cerr << "mn : " << get(1,len).first << ' ' << get(1,len).second << '\n';
}
// cerr << head->mn << ' ' << head->cnt << '\n';
return get(1,len).second;
}