제출 #202314

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
202314		errorgorn	Seats (IOI18_seats)	C++14	0 / 100	4083 ms	217868 KiB

seats

    #include "seats.h"
    #include <bits/stdc++.h>
    using namespace std;
    typedef pair<int,int> ii;
     
     
    struct node{
    	int s,e,m;
    	int minv,maxv;
    	node *l, *r;
    	
    	node (int _s,int _e){
    		s=_s,e=_e,m=s+e>>1;
    		
    		if (s!=e){
    			l=new node(s,m);
    			r=new node(m+1,e);
    		}
    	}
    	
    	int query_min(int i,int j){
    		if (s==i && e==j) return minv;
    		else if (j<=m) return l->query_min(i,j);
    		else if (m<i) return r->query_min(i,j);
    		else return min(l->query_min(i,m),r->query_min(m+1,j));
    	}
    	
    	int query_max(int i,int j){
    		if (s==i && e==j) return maxv;
    		else if (j<=m) return l->query_max(i,j);
    		else if (m<i) return r->query_max(i,j);
    		else return max(l->query_max(i,m),r->query_max(m+1,j));
    	}
    	
    	void update(int i,int j){
    		if (s==e) minv=maxv=j;
    		else{
    			if (i<=m) l->update(i,j);
    			else r->update(i,j);
    			
    			minv=min(l->minv,r->minv);
    			maxv=max(l->maxv,r->maxv);
    		}
    	}
    };
     
    int h,w;
    ii pos[1000005];
    int grid[1005][1005];
     
    node* hor[1005];
    node* ver[1005];
     
    void print(){
    	for (int x=0;x<h;x++){
    		for (int y=0;y<w;y++) printf("%d ",grid[x][y]);
    		printf("\n");
    	}
    	printf("\n");
    }
     
    void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    	for (int x=0;x<1005;x++) hor[x]=new node(0,1005),ver[x]=new node(0,1005);
    	
    	h=H,w=W;
    	for (int x=0;x<h*w;x++){
    		grid[R[x]][C[x]]=x;
    		pos[x]=ii(R[x],C[x]);
    		ver[pos[x].first]->update(pos[x].second,x);
    		hor[pos[x].second]->update(pos[x].first,x);
    	}
    	
    	//print();
    }
     
    int swap_seats(int a, int b) {
    	swap(grid[pos[a].first][pos[a].second],grid[pos[b].first][pos[b].second]);
    	swap(pos[a],pos[b]);
    	
    	ver[pos[a].first]->update(pos[a].second,a);
    	hor[pos[a].second]->update(pos[a].first,a);
    	
    	ver[pos[b].first]->update(pos[b].second,b);
    	hor[pos[b].second]->update(pos[b].first,b);
    	
    	//print();
    	
    	int x1,x2,y1,y2;
    	x1=x2=pos[0].first;
    	y1=y2=pos[0].second;
    	
    	int s=1;
    	int biggest=0;
    	int res=1;
    	while (s<h*w){
    		int best=1000000000,tmp;
    		int dir=-1;
    		
    		if (0<x1){
    			tmp=ver[x1-1]->query_min(y1,y2);
    			if (tmp<best){
    				best=tmp;
    				dir=0;
    			}
    		}
    		if (x2<w-1){
    			tmp=ver[x2+1]->query_min(y1,y2);
    			if (tmp<best){
    				best=tmp;
    				dir=1;
    			}
    		}
    		if (0<y1){
    			tmp=hor[y1-1]->query_min(x1,x2);
    			if (tmp<best){
    				best=tmp;
    				dir=2;
    			}
    		}
    		if (y2<h-1){
    			tmp=hor[y2+1]->query_min(x1,x2);
    			if (tmp<best){
    				best=tmp;
    				dir=3;
    			}
    		}
    		
    		if (dir==0){
    			x1--;
    			s+=y2-y1+1;
    			biggest=max(biggest,ver[x1]->query_max(y1,y2));
    		}
    		else if (dir==1){
    			x2++;
    			s+=y2-y1+1;
    			biggest=max(biggest,ver[x2]->query_max(y1,y2));
    		}
    		else if (dir==2){
    			y1--;
    			s+=x2-x1+1;
    			biggest=max(biggest,hor[y1]->query_max(x1,x2));
    		}
    		else{
    			y2++;
    			s+=x2-x1+1;
    			biggest=max(biggest,hor[y2]->query_max(x1,x2));
    		}
    		
    		if (biggest==s-1) res++;
    		//printf("DEBUG: %d %d\n",biggest,s);
    		//printf("DEBUG: %d %d %d %d\n",x1,x2,y1,y2);
    	}
    	
    	return res;
    }

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

seats.cpp: In constructor 'node::node(int, int)':
seats.cpp:13:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       s=_s,e=_e,m=s+e>>1;
                   ~^~

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