제출 #422002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422002		Bill_00	자리 배치 (IOI18_seats)	C++14	0 / 100	4103 ms	210360 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define INF INT_MAX
using namespace std;
int lazy[4000000][2],r[1000000],c[1000000],a[4000000],H,W;
vector<pair<pair<int,int>,int>>node[4000000];
vector<pair<pair<int,int>,int> >combine(vector<pair<pair<int,int>,int> >l,vector<pair<pair<int,int>,int> >r){
	map<pair<int,int>,int>um;
	vector<pair<pair<int,int>,int> >ans;
	vector<pair<int,int> >p;
	for(int i=0;i<l.size();i++){
		p.push_back(l[i].ff);
		um[l[i].ff]=l[i].ss;
	}
	for(int i=0;i<r.size();i++){
		p.push_back(r[i].ff);
		um[r[i].ff]+=r[i].ss;
	}
	sort(p.begin(),p.end());
	for(int i=0;i<p.size();i++){
		if(ans.size()==0 || ans.back().ff!=p[i]){
			ans.push_back({p[i],um[p[i]]});
		}
		if(ans.size()==5) break;
	}
	return ans;
}
void build(int id,int l,int r){
	if(l==r){
		node[id].push_back({{0,0},1});
		return;
	}
	int m=l+r>>1;
	build(id*2,l,m);
	build(id*2+1,m+1,r);
	node[id]=combine(node[id*2],node[id*2+1]);
}
void update(int id,int l,int r,int L,int R,bool type,int val){
	if(type==0){
		for(int i=0;i<node[id].size();i++){
			node[id][i].ff.ss+=lazy[id][type];
		}
		if(l!=r){
			lazy[id*2][type]+=lazy[id][type];
			lazy[id*2+1][type]+=lazy[id][type];
		}
		lazy[id][type]=0;
	}	
	else{
		for(int i=0;i<node[id].size();i++){
			node[id][i].ff.ff+=lazy[id][type];
		}
		if(l!=r){
			lazy[id*2][type]+=lazy[id][type];
			lazy[id*2+1][type]+=lazy[id][type];
		}
		lazy[id][type]=0;
	}
	if(r<L || R<l) return;
	if(L<=l && r<=R){
		for(int i=0;i<node[id].size();i++){
			if(type) node[id][i].ff.ff+=val;
			else node[id][i].ff.ss+=val;
		}
		if(l!=r){
			lazy[id*2][type]+=val;
			lazy[id*2+1][type]+=val;
		}
		return;
	}
	int m=l+r>>1;
	update(id*2,l,m,L,R,type,val);
	update(id*2+1,m+1,r,L,R,type,val);
	node[id]=combine(node[id*2],node[id*2+1]);
}
void give_initial_chart(int h, int w,vector<int> R,vector<int> C){
	H=h;
	W=w;
	build(1,0,H*W-1);
	for(int i=0;i<R.size();i++){
		r[i]=R[i]+1;
		c[i]=C[i]+1;
		a[(R[i]+1)*(W+2)+C[i]+1]=i;
		// cout << R[i]+1 << ' ' << C[i]+1 << ' ' << (R[i]+1)*(W+2)+C[i]+1 << '\n';
	}
	for(int i=0;i<=W+1;i++){
		a[i]=INF;
		a[(H+1)*(W+2)+i]=INF;
	}
	for(int i=0;i<=H+1;i++){
		a[i*(W+2)]=INF;
		a[i*(W+2)+W+1]=INF;
	}
	for(int i=1;i<=H+1;i++){
		for(int j=1;j<=W+1;j++){
			vector<int>v;
			v.push_back(a[i*(W+2)+j]);
			v.push_back(a[(i-1)*(W+2)+j]);
			v.push_back(a[i*(W+2)+j-1]);
			v.push_back(a[(i-1)*(W+2)+j-1]);
			sort(v.begin(),v.end());
			// printf("%d %d %d %d %d\n",v[0],v[1],v[2],v[3],101000000);
			update(1,0,H*W-1,v[0],min(v[1],H*W)-1,0,1);
			if(v[2]!=INF) update(1,0,H*W-1,v[2],min(H*W,v[3])-1,1,1);
		}
	}
}
pair<int,int>answer={0,4};
int swap_seats(int A, int B){
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			int x=r[A]+i;
			int y=c[A]+j;
			vector<int>v;
			v.push_back(a[x*(W+2)+y]);
			v.push_back(a[(x-1)*(W+2)+y]);
			v.push_back(a[x*(W+2)+y-1]);
			v.push_back(a[(x-1)*(W+2)+y-1]);
			sort(v.begin(),v.end());
			update(1,0,H*W-1,v[0],min(v[1],H*W)-1,0,-1);
			if(v[2]!=INF) update(1,0,H*W-1,v[2],min(H*W,v[3])-1,1,-1);
		}
	}
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			int x=r[B]+i;
			int y=c[B]+j;
			vector<int>v;
			v.push_back(a[x*(W+2)+y]);
			v.push_back(a[(x-1)*(W+2)+y]);
			v.push_back(a[x*(W+2)+y-1]);
			v.push_back(a[(x-1)*(W+2)+y-1]);
			sort(v.begin(),v.end());
			update(1,0,H*W-1,v[0],min(v[1],H*W)-1,0,-1);
			if(v[2]!=INF) update(1,0,H*W-1,v[2],min(H*W,v[3])-1,1,-1);
		}
	}
	swap(a[r[A]*(W+2)+c[A]],a[r[B]*(W+2)+c[B]]);
	swap(r[A],r[B]);
	swap(c[A],c[B]);
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			int x=r[A]+i;
			int y=c[A]+j;
			vector<int>v;
			v.push_back(a[x*(W+2)+y]);
			v.push_back(a[(x-1)*(W+2)+y]);
			v.push_back(a[x*(W+2)+y-1]);
			v.push_back(a[(x-1)*(W+2)+y-1]);
			sort(v.begin(),v.end());
			update(1,0,H*W-1,v[0],min(v[1],H*W)-1,0,1);
			if(v[2]!=INF) update(1,0,H*W-1,v[2],min(H*W,v[3])-1,1,1);
		}
	}
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			int x=r[B]+i;
			int y=c[B]+j;
			vector<int>v;
			v.push_back(a[x*(W+2)+y]);
			v.push_back(a[(x-1)*(W+2)+y]);
			v.push_back(a[x*(W+2)+y-1]);
			v.push_back(a[(x-1)*(W+2)+y-1]);
			sort(v.begin(),v.end());
			update(1,0,H*W-1,v[0],min(v[1],H*W)-1,0,1);
			if(v[2]!=INF) update(1,0,H*W-1,v[2],min(H*W,v[3])-1,1,1);
		}
	}
	for(pair<pair<int,int>,int>to:node[1]){
		if(to.ff==answer) return to.ss;
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

seats.cpp: In function 'std::vector<std::pair<std::pair<int, int>, int> > combine(std::vector<std::pair<std::pair<int, int>, int> >, std::vector<std::pair<std::pair<int, int>, int> >)':
seats.cpp:13:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(int i=0;i<l.size();i++){
      |              ~^~~~~~~~~
seats.cpp:17:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0;i<r.size();i++){
      |              ~^~~~~~~~~
seats.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
seats.cpp: In function 'void build(int, int, int)':
seats.cpp:35:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |  int m=l+r>>1;
      |        ~^~
seats.cpp: In function 'void update(int, int, int, int, int, bool, int)':
seats.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int i=0;i<node[id].size();i++){
      |               ~^~~~~~~~~~~~~~~~
seats.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0;i<node[id].size();i++){
      |               ~^~~~~~~~~~~~~~~~
seats.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i=0;i<node[id].size();i++){
      |               ~^~~~~~~~~~~~~~~~
seats.cpp:73:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |  int m=l+r>>1;
      |        ~^~
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int i=0;i<R.size();i++){
      |              ~^~~~~~~~~

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