Submission #121493

#	Time	Username	Problem	Language	Result	Execution time	Memory
121493		TadijaSebez	Seats (IOI18_seats)	C++11	100 / 100	2924 ms	212348 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N=1000050;
const int M=2*N;
const int inf=2e6;
int ls[M],rs[M],cnt[M],root,tsz,n;
ll mn[M],lzy[M],val[N];
void Build(int &c, int ss, int se)
{
	c=++tsz;mn[c]=lzy[c]=0;cnt[c]=se-ss+1;
	if(ss==se){ mn[c]=val[ss];return;}
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
	mn[c]=min(mn[ls[c]],mn[rs[c]]);
    cnt[c]=0;
    if(mn[c]==mn[ls[c]]) cnt[c]+=cnt[ls[c]];
    if(mn[c]==mn[rs[c]]) cnt[c]+=cnt[rs[c]];
}
void Push(int c, int ss, int se)
{
	if(!lzy[c]) return;
	if(ss!=se)
	{
		lzy[ls[c]]+=lzy[c];mn[ls[c]]+=lzy[c];
		lzy[rs[c]]+=lzy[c];mn[rs[c]]+=lzy[c];
	}
	lzy[c]=0;
}
void Inc(int c, int ss, int se, int qs, int qe, int f)
{
    if(qs>se || ss>qe || qs>qe) return;
    if(qs<=ss && qe>=se){ lzy[c]+=f;mn[c]+=f;return;}
    int mid=ss+se>>1;
    Push(c,ss,se);
    Inc(ls[c],ss,mid,qs,qe,f);
    Inc(rs[c],mid+1,se,qs,qe,f);
    mn[c]=min(mn[ls[c]],mn[rs[c]]);
    cnt[c]=0;
    if(mn[c]==mn[ls[c]]) cnt[c]+=cnt[ls[c]];
    if(mn[c]==mn[rs[c]]) cnt[c]+=cnt[rs[c]];
}
int Get(){ return cnt[root]*(mn[root]==4);}
vector<vector<int> > matrix,add;
int x[N],y[N];
void Add(int x, int y, int f)
{
	if(add[x][y]+f>1 || add[x][y]+f<0) return;
	add[x][y]+=f;
	vector<int> v={matrix[x][y],matrix[x+1][y],matrix[x][y+1],matrix[x+1][y+1]};
	sort(v.begin(),v.end());
	Inc(root,0,n-1,v[0],v[1]-1,f);
	Inc(root,0,n-1,v[2],v[3]-1,f*inf);
}
ll inc[N];
void Put(int x, int y, int f)
{
	if(add[x][y]+f>1 || add[x][y]+f<0) return;
	add[x][y]+=f;
	vector<int> v={matrix[x][y],matrix[x+1][y],matrix[x][y+1],matrix[x+1][y+1]};
	sort(v.begin(),v.end());
	//Inc(root,0,n-1,v[0],v[1]-1,f);
	//Inc(root,0,n-1,v[2],v[3]-1,f*inf);
	inc[v[0]]+=f;inc[v[1]]-=f;
	inc[v[2]]+=f*inf;inc[v[3]]-=f*inf;
}
void Solve(int n)
{
	ll tmp=0;
	for(int i=0;i<n;i++) tmp+=inc[i],val[i]=tmp;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
	n=H*W;
	matrix.resize(H+2);for(int i=0;i<matrix.size();i++) matrix[i].resize(W+2);
	add.resize(H+2);for(int i=0;i<add.size();i++) add[i].resize(W+2);
	for(int i=0;i<matrix.size();i++) for(int j=0;j<matrix[i].size();j++) matrix[i][j]=n;
	for(int i=0;i<n;i++) x[i]=R[i]+1,y[i]=C[i]+1,matrix[x[i]][y[i]]=i;
	for(int i=0;i<=H;i++) for(int j=0;j<=W;j++) Put(i,j,1);
	Solve(n);
	Build(root,0,n-1);
}
void AddPt(int x, int y, int f)
{
	Add(x-1,y-1,f);
	Add(x-1,y,f);
	Add(x,y-1,f);
	Add(x,y,f);
}
int swap_seats(int a, int b)
{
	AddPt(x[a],y[a],-1);
	AddPt(x[b],y[b],-1);
	swap(matrix[x[a]][y[a]],matrix[x[b]][y[b]]);
	swap(x[a],x[b]);
	swap(y[a],y[b]);
	AddPt(x[a],y[a],1);
	AddPt(x[b],y[b],1);
	return Get();
}
/*int BruteForce(int H, int W, vector<int> R, vector<int> C)
{
	int n=H*W;
	int xl=n,xr=-1,yl=n,yr=-1,ans=0;
    for(int i=0;i<n;i++)
	{
		xl=min(xl,R[i]);
		xr=max(xr,R[i]);
		yl=min(yl,C[i]);
		yr=max(yr,C[i]);
		if(i+1==(xr-xl+1)*(yr-yl+1)) ans++;
	}
	return ans;
}
void StressTest()
{
	srand(time(0));
	int t=1000;
	while(t--)
	{
		int n=rand()%1000+1;
		vector<int> R,C;R.resize(n);C.resize(n);
		for(int i=0;i<n;i++) C[i]=i;
		random_shuffle(C.begin(),C.end());
		give_initial_chart(1,n,R,C);
		int sol=Get(),ans=BruteForce(1,n,R,C);
        if(sol!=ans)
		{
            printf("%i\n",n);
            for(int i=0;i<n;i++) printf("%i ",C[i]);printf("\n");
            printf("my:%i brute:%i\n",sol,ans);
            return;
		}
	}
	printf("OK\n");
}
int main()
{
	StressTest();
	return 0;
}*/

Compilation message (stderr)

seats.cpp: In function 'void Build(int&, int, int)':
seats.cpp:15:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
seats.cpp: In function 'void Inc(int, int, int, int, int, int)':
seats.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=ss+se>>1;
             ~~^~~
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:78:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  matrix.resize(H+2);for(int i=0;i<matrix.size();i++) matrix[i].resize(W+2);
                                 ~^~~~~~~~~~~~~~
seats.cpp:79:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  add.resize(H+2);for(int i=0;i<add.size();i++) add[i].resize(W+2);
                              ~^~~~~~~~~~~
seats.cpp:80:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<matrix.size();i++) for(int j=0;j<matrix[i].size();j++) matrix[i][j]=n;
              ~^~~~~~~~~~~~~~
seats.cpp:80:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<matrix.size();i++) for(int j=0;j<matrix[i].size();j++) matrix[i][j]=n;
                                               ~^~~~~~~~~~~~~~~~~

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