제출 #294486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
294486		amiratou	자리 배치 (IOI18_seats)	C++14	37 / 100	4014 ms	68600 KiB

seats

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(x) (int)(x.size())
const int MX = (int)(1e6+3);
const int INF = (int)(1e9);
typedef pair<int,int> ii;

int ans[MX],sum[4*MX],lazy[4*MX],fen[MX],N;
vector<int> X,Y;
bool flag;
ii range[MX][2];
pair<ii,ii> st[4*MX];
void add(int idx,int val){
	for (int i = idx; i <= N; i+=(i&(-i)))
		fen[i]+=val;
}
int get(int idx){
	int h=0;
	for (int i = idx; i >= 1; i-=(i&(-i)))
		h+=fen[i];
	return h;
}
int fquery(int a,int b){
	return get(b)-get(a-1);
}
void build(int node,int l,int r){
	if(l==r){
		st[node]={{X[l],X[l]},{Y[l],Y[l]}};
		return;
	}
	int med=(l+r)>>1;
	build(node*2,l,med),build(node*2+1,med+1,r);
	st[node].fi={min(st[node*2].fi.fi,st[node*2+1].fi.fi),max(st[node*2].fi.se,st[node*2+1].fi.se)};
	st[node].se={min(st[node*2].se.fi,st[node*2+1].se.fi),max(st[node*2].se.se,st[node*2+1].se.se)};
}
void update(int node,int l,int r,int idx){
	if(l>idx || r<idx)
		return;
	if(l==r){
		st[node]={{X[l],X[l]},{Y[l],Y[l]}};
		return;
	}
	int med=(l+r)>>1;
	update(node*2,l,med,idx),update(node*2+1,med+1,r,idx);
	st[node].fi={min(st[node*2].fi.fi,st[node*2+1].fi.fi),max(st[node*2].fi.se,st[node*2+1].fi.se)};
	st[node].se={min(st[node*2].se.fi,st[node*2+1].se.fi),max(st[node*2].se.se,st[node*2+1].se.se)};
}
void push(int node,int l,int r){
	if(lazy[node]){
		lazy[node]--;
		sum[node]=(r-l+1)*lazy[node];
		if(l!=r){
			lazy[node*2]=lazy[node]+1;
			lazy[node*2+1]=lazy[node]+1;
		}
		lazy[node]=0;	}
}
void supdate(int node,int l,int r,int i,int j,int val){
	push(node,l,r);
	if(l>j || r<i)return;
	if(l>=i && r<=j){
		lazy[node]=val+1;
		push(node,l,r);
		return;
	}
	int med=(l+r)>>1;
	supdate(node*2,l,med,i,j,val),supdate(node*2+1,med+1,r,i,j,val);
	sum[node]=sum[node*2]+sum[node*2+1];
}
int squery(int node,int l,int r,int i,int j){
	push(node,l,r);
	if(l>j || r<i)return 0;
	if(l>=i && r<=j)return sum[node];
	int med=(l+r)>>1;
	return squery(node*2,l,med,i,j)+squery(node*2+1,med+1,r,i,j);
}
pair<ii,ii> query(int node,int l,int r,int i,int j){
	if(l>j || r<i)
		return {{INF,-1},{INF,-1}};
	if(l>=i && r<=j)return st[node];
	int med=(l+r)>>1;
	pair<ii,ii> q=query(node*2,l,med,i,j),q2=query(node*2+1,med+1,r,i,j);
	return {{min(q.fi.fi,q2.fi.fi),max(q.fi.se,q2.fi.se)},{min(q.se.fi,q2.se.fi),max(q.se.se,q2.se.se)}};
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	X=R,Y=C;
	N=sz(X);
	if(max(H,W)<=1000)flag=1;
	if(flag)build(1,0,N-1);
	for (int i = 0; i < H*W;)
	{
		if(!flag){
			range[i][0]=range[i][1]={INF,-1};
			if(i){
				range[i][0].fi=min(range[i][0].fi,range[i-1][0].fi);
				range[i][0].se=max(range[i][0].se,range[i-1][0].se);
				range[i][1].fi=min(range[i][1].fi,range[i-1][1].fi);
				range[i][1].se=max(range[i][1].se,range[i-1][1].se);
			}
			range[i][0].fi=min(range[i][0].fi,R[i]);
			range[i][0].se=max(range[i][0].se,R[i]);
			range[i][1].fi=min(range[i][1].fi,C[i]);
			range[i][1].se=max(range[i][1].se,C[i]);
			if(((range[i][0].se-range[i][0].fi+1)*(range[i][1].se-range[i][1].fi+1))==(i+1))add(i+1,1);
			i++;continue;
		}
		pair<ii,ii> q=query(1,0,N-1,0,i);
		if(((q.fi.se-q.fi.fi+1)*(q.se.se-q.se.fi+1))==(i+1))supdate(1,0,N-1,i,i,1),i++;
		else i=((q.fi.se-q.fi.fi+1)*(q.se.se-q.se.fi+1))-1;
	}
}

int swap_seats(int a, int b) {
	if(a>b)swap(a,b);
	swap(X[a],X[b]),swap(Y[a],Y[b]);
	if(flag){	
		update(1,0,N-1,a),update(1,0,N-1,b);
		supdate(1,0,N-1,a,b,0);
	}
	for (int i = a; i <= b;)
	{
		if(!flag){
			if(fquery(i+1,i+1))add(i+1,-1);
			range[i][0]=range[i][1]={INF,-1};
			if(i){
				range[i][0].fi=min(range[i][0].fi,range[i-1][0].fi);
				range[i][0].se=max(range[i][0].se,range[i-1][0].se);
				range[i][1].fi=min(range[i][1].fi,range[i-1][1].fi);
				range[i][1].se=max(range[i][1].se,range[i-1][1].se);
			}
			range[i][0].fi=min(range[i][0].fi,X[i]);
			range[i][0].se=max(range[i][0].se,X[i]);
			range[i][1].fi=min(range[i][1].fi,Y[i]);
			range[i][1].se=max(range[i][1].se,Y[i]);
			if(((range[i][0].se-range[i][0].fi+1)*(range[i][1].se-range[i][1].fi+1))==(i+1))add(i+1,1);
			i++;continue;
		}
		pair<ii,ii> q=query(1,0,N-1,0,i);
		if(((q.fi.se-q.fi.fi+1)*(q.se.se-q.se.fi+1))==(i+1))supdate(1,0,N-1,i,i,1),i++;
		else i=((q.fi.se-q.fi.fi+1)*(q.se.se-q.se.fi+1))-1;
	}
	if(!flag)return fquery(1,N);
	return squery(1,0,N-1,0,N-1);
}

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