oj.uz

Submission #127535

# Submission time Handle Problem Language Result Execution time Memory
127535 2019-07-09T14:05:28 Z nxteru Wall (IOI14_wall) C++14
61 / 100
 719 ms 90852 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 100001
#define PB push_back
struct node{
	int d,u;
	void ini(void){
		d=0,u=INF;
	}
	node operator +(const node &q)const{
		if(d>=q.u)return node{q.u,q.u};
		else if(u<=q.d)return node{q.d,q.d};
		else return node{max(d,q.d),min(u,q.u)};
	}
};
struct SEG{
	node seg[1<<20];
	SEG(void){
		for(int i=0;i<1<<20;i++){
			seg[i].ini();
		}
	}
	void up(int a,node x){
		a+=(1<<19)-1;
		seg[a]=x;
		while(a>0){
			a=(a-1)/2;
			seg[a]=seg[a*2+1]+seg[a*2+2];
		}
	}
	int que(void){
		return seg[0].d;
	}
};
SEG seg;
vector<int>in[500005],out[500005];
void buildWall(int n,int k,int t[],int l[],int r[],int h[],int ans[]){
	for(int i=0;i<k;i++)in[l[i]].PB(i),out[r[i]+1].PB(i);
	for(int i=0;i<n;i++){
		for(int j=0;j<in[i].size();j++){
			int x=in[i][j];
			node p;
			p.ini();
			if(t[x]==1)p.d=h[x];
			else p.u=h[x];
			seg.up(x,p);
		}
		for(int j=0;j<out[i].size();j++){
			node p;
			p.ini();
			seg.up(out[i][j],p);
		}
		ans[i]=seg.que();
	}
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<in[i].size();j++){
               ~^~~~~~~~~~~~~
wall.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<out[i].size();j++){
               ~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 31992 KB Output is correct
2 Correct 33 ms 32248 KB Output is correct
3 Correct 34 ms 31992 KB Output is correct
4 Correct 43 ms 32504 KB Output is correct
5 Correct 36 ms 32504 KB Output is correct
6 Correct 36 ms 32508 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 31956 KB Output is correct
2 Correct 252 ms 49860 KB Output is correct
3 Correct 207 ms 42488 KB Output is correct
4 Correct 622 ms 59572 KB Output is correct
5 Correct 323 ms 58360 KB Output is correct
6 Correct 318 ms 56568 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31992 KB Output is correct
2 Correct 33 ms 32248 KB Output is correct
3 Correct 32 ms 32108 KB Output is correct
4 Correct 36 ms 32552 KB Output is correct
5 Correct 36 ms 32376 KB Output is correct
6 Correct 36 ms 32384 KB Output is correct
7 Correct 30 ms 31996 KB Output is correct
8 Correct 252 ms 49848 KB Output is correct
9 Correct 202 ms 42488 KB Output is correct
10 Correct 644 ms 59632 KB Output is correct
11 Correct 321 ms 58360 KB Output is correct
12 Correct 322 ms 56472 KB Output is correct
13 Correct 30 ms 31992 KB Output is correct
14 Correct 286 ms 49836 KB Output is correct
15 Correct 64 ms 34040 KB Output is correct
16 Correct 719 ms 59896 KB Output is correct
17 Correct 375 ms 56672 KB Output is correct
18 Correct 376 ms 56440 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31996 KB Output is correct
2 Correct 33 ms 32220 KB Output is correct
3 Correct 32 ms 32120 KB Output is correct
4 Correct 36 ms 32504 KB Output is correct
5 Correct 35 ms 32376 KB Output is correct
6 Correct 35 ms 32480 KB Output is correct
7 Correct 30 ms 31992 KB Output is correct
8 Correct 252 ms 49852 KB Output is correct
9 Correct 205 ms 42616 KB Output is correct
10 Correct 628 ms 59680 KB Output is correct
11 Correct 323 ms 58360 KB Output is correct
12 Correct 323 ms 56472 KB Output is correct
13 Correct 30 ms 32120 KB Output is correct
14 Correct 288 ms 49804 KB Output is correct
15 Correct 63 ms 34040 KB Output is correct
16 Correct 697 ms 59768 KB Output is correct
17 Correct 379 ms 56648 KB Output is correct
18 Correct 375 ms 56472 KB Output is correct
19 Runtime error 274 ms 90852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -