제출 #1066856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1066856		Muhammad_Aneeq	자리 배치 (IOI18_seats)	C++17	0 / 100	3480 ms	64120 KiB

seats

#pragma GCC optimze("O2")
#include <vector>
#include <iostream>
using namespace std;
int h,w;
int const N=1e6+10;
struct node
{
	int mx=0,my=0,mix=1e9,miy=1e9;	
};
pair<int,int>seat[N]={};
node St[2097152]={};
bool fen[N]={};
node extra;
void add(int x,int val)
{
	while (x<h*w)
	{
		fen[x]+=val;
		x=(x|(x+1));
	}
}
int get(int r)
{
	int s=0;
	while (r>=0)
	{
		s+=fen[r];
		r=(r&(r+1))-1;
	}
	return s;
}
int sum(int l,int r)
{
	return get(r)-get(l-1);
}
node comb(node a,node b)
{
	node c;
	c.mx=max(a.mx,b.mx);
	c.mix=min(a.mix,b.mix);
	c.my=max(a.my,b.my);
	c.miy=min(a.miy,b.miy);
	return c;
}
int ans=0;
void build(int i,int st,int en)
{
	if (st==en)
	{
		St[i].mx=St[i].mix=seat[st].first;
		St[i].my=St[i].miy=seat[st].second;
		return;
	}
	int mid=(st+en)/2;
	St[i]=comb(St[i*2],St[i*2+1]);
}
void update(int i,int r,int st,int en)
{
	if (st==en)
	{
		St[i].mx=St[i].mix=seat[st].first;
		St[i].my=St[i].miy=seat[st].second;
		return;
	}
	int mid=(st+en)/2;
	if (r<=mid)
		update(i*2,r,st,mid);
	else
		update(i*2+1,r,mid+1,en);
	St[i]=comb(St[i*2],St[i*2+1]);
}
node get(int i,int st,int en,int l,int r)
{
	if (l>r)
		return extra;
	if (st>=l&&en<=r)
		return St[i];
	if (st>r||en<l)
		return extra;
	int mid=(st+en)/2;
	return comb(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
	h=H,w=W;
	for (int i=0;i<H*W;i++)
		seat[i]={R[i],C[i]};
	build(1,0,h*w-1);
	int x=0,mx=1e9;
	int y=0,my=1e9;
	for (int k=0;k<h*w;k++)
	{
		x=max(x,seat[k].first);
		mx=min(mx,seat[k].first);
		y=max(y,seat[k].second);
		my=min(my,seat[k].second);
		if ((x-mx+1)*(y-my+1)==k+1)
		{
			fen[k]=1;
			ans++;
		}
	}
}
int swap_seats(int a, int b)
{
	swap(seat[a],seat[b]);
	update(1,a,0,h*w-1);
	update(1,b,0,h*w-1);
	int x=0,mx=1e9;
	int y=0,my=1e9;
	node z=get(1,0,h*w,0,min(a,b)-1);
	x=z.mx,y=z.my;
	mx=z.mix,my=z.miy;
	for (int k=min(a,b);k<=max(a,b);k++)
	{
		x=max(x,seat[k].first);
		mx=min(mx,seat[k].first);
		y=max(y,seat[k].second);
		my=min(my,seat[k].second);
		if ((x-mx+1)*(y-my+1)==k+1)
		{
			if (fen[k]==0)
				ans++;
			fen[k]=1;
		}
		else if (fen[k])
		{
			fen[k]=0;
			ans--;
		}
	}
	return ans;
}

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

seats.cpp:1: warning: ignoring '#pragma GCC optimze' [-Wunknown-pragmas]
    1 | #pragma GCC optimze("O2")
      | 
seats.cpp: In function 'void build(int, int, int)':
seats.cpp:55:6: warning: unused variable 'mid' [-Wunused-variable]
   55 |  int mid=(st+en)/2;
      |      ^~~

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