Submission #960604

#	Time	Username	Problem	Language	Result	Execution time	Memory
960604		kim	Wall (IOI14_wall)	C++17	24 / 100	877 ms	17544 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back

struct segment{
	int a[1<<20],lz[1<<20][2],l0,r0;
	bitset<1<<20> b;
	void build(int i,int il,int ir){
		lz[i][0]=lz[i][1]=-1;
		if(il==ir) return;
		int im=il+ir>>1;
		build(i<<1,il,im), build(i<<1|1,im+1,ir);
	}
	void init(int l,int r){
		l0=l,r0=r;
		build(1,l,r);
	}
	void flush(int i,int il,int ir){
		bool op=!b[i];
		if(lz[i][op]!=-1){
			if(il!=ir){
				if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
				if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
			}
			else{
				if(op==0) a[i]=max(a[i],lz[i][op]);
				else a[i]=min(a[i],lz[i][op]);
			}
			lz[i][op]=-1;
		}
		op^=1;
		if(lz[i][op]!=-1){
			if(il!=ir){
				if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
				if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
			}
			else{
				if(op==0) a[i]=max(a[i],lz[i][op]);
				else a[i]=min(a[i],lz[i][op]);
			}
			lz[i][op]=-1;
		}
	}
	void upd(int i,int il,int ir,int l,int r,int op,int v){
		flush(i,il,ir);
		if(l<=il&&ir<=r){
			if(lz[i][op]==-1 || op==0&&lz[i][op]<v || op==1&&lz[i][op]>v) lz[i][op]=v, b[i]=op, flush(i,il,ir);
			return;
		}
		if(il>r||ir<l) return;
		int im=il+ir>>1;
		upd(i<<1,il,im,l,r,op,v), upd(i<<1|1,im+1,ir,l,r,op,v);
	}
	void upd(int l,int r,int op,int v){upd(1,l0,r0,l,r,op,v);}
	int qr(int i,int il,int ir,int x){
		flush(i,il,ir);
		if(il==ir) return a[i];
		int im=il+ir>>1;
		if(x<=im) return qr(i<<1,il,im,x);
		return qr(i<<1|1,im+1,ir,x);
	}
	int qr(int i){return qr(1,l0,r0,i);}
}t;

void buildWall(int n, int k, int op[], int L[], int R[], int H[], int ans[]){
	vector<int> comp;
	for(int i=0;i<k;++i) comp.eb(L[i]),comp.eb(++R[i]);
	comp.eb(0),comp.eb(n);
	sort(comp.begin(),comp.end());
	comp.erase(unique(comp.begin(),comp.end()),comp.end());

	t.init(0,comp.size());
	for(int i=0;i<k;++i){
		L[i]=lower_bound(comp.begin(),comp.end(),L[i])-comp.begin();
		R[i]=lower_bound(comp.begin(),comp.end(),R[i])-comp.begin()-1;
		t.upd(L[i],R[i],op[i]-1,H[i]);
	}
	for(int i=0,j=0;i+1<comp.size();++i){
		for(;j<comp[i+1];++j) ans[j]=t.qr(i);
	}
}

Compilation message (stderr)

wall.cpp: In member function 'void segment::build(int, int, int)':
wall.cpp:12:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |   int im=il+ir>>1;
      |          ~~^~~
wall.cpp: In member function 'void segment::flush(int, int, int)':
wall.cpp:23:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   23 |     if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:23:66: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   23 |     if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
      |                                                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:24:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   24 |     if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:24:70: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   24 |     if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
      |                                                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:35:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |     if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:35:66: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |     if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
      |                                                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:36:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   36 |     if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:36:70: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   36 |     if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
      |                                                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp: In member function 'void segment::upd(int, int, int, int, int, int, int)':
wall.cpp:48:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |    if(lz[i][op]==-1 || op==0&&lz[i][op]<v || op==1&&lz[i][op]>v) lz[i][op]=v, b[i]=op, flush(i,il,ir);
      |                        ~~~~~^~~~~~~~~~~~~
wall.cpp:48:51: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |    if(lz[i][op]==-1 || op==0&&lz[i][op]<v || op==1&&lz[i][op]>v) lz[i][op]=v, b[i]=op, flush(i,il,ir);
      |                                              ~~~~~^~~~~~~~~~~~~
wall.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int im=il+ir>>1;
      |          ~~^~~
wall.cpp: In member function 'int segment::qr(int, int, int, int)':
wall.cpp:59:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |   int im=il+ir>>1;
      |          ~~^~~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i=0,j=0;i+1<comp.size();++i){
      |                  ~~~^~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39