oj.uz

Submission #88412

# Submission time Handle Problem Language Result Execution time Memory
88412 2018-12-05T17:38:05 Z Pajaraja Wall (IOI14_wall) C++17
0 / 100
 2 ms 692 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define MAXN 1000007
using namespace std;
pair<int,int> seg[4*MAXN];
bool a[4*MAXN];
int poz[MAXN];
void loc(int l,int r,int ind)
{
	if(l==r) {poz[l]=ind; return;}
	int s=(l+r)/2; loc(l,s,2*ind); loc(s+1,r,2*ind+1);
}
void upd(int l,int r,int lt, int rt,int val,bool b,int x,int ind)
{
	if(r<lt || l>rt) return;
	if(l>=lt && r<=rt)
	{
		if(b) seg[ind].second=max(seg[ind].second,val);
		else seg[ind].second=min(seg[ind].second,val);
		seg[ind].first=x;
		a[ind]=b;
		return;
	}
	int s=(l+r)/2;
	upd(l,s,lt,rt,val,b,x,2*ind); upd(s+1,r,lt,rt,val,b,x,2*ind+1); 
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	loc(0,n-1,1);
	for(int i=0;i<k;i++) upd(0,n-1,left[i],right[i],height[i],op[i]==1,i,1);
	for(int i=0;i<n;i++) 
	{
		vector<pair<pair<int,int>,bool> > arr;
		while(poz[i]!=0) {if(seg[poz[i]].first!=0) arr.push_back(make_pair(seg[poz[i]],a[poz[i]])); poz[i]/=2;}
		sort(arr.begin(),arr.end());
		if(arr.size()>0) finalHeight[i]=arr[0].first.second;
		for(int j=1;j<arr.size();j++) {if(arr[j].second) finalHeight[i]=max(finalHeight[i],arr[j].first.second); else finalHeight[i]=min(finalHeight[i],arr[j].first.second);}
	}
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1;j<arr.size();j++) {if(arr[j].second) finalHeight[i]=max(finalHeight[i],arr[j].first.second); else finalHeight[i]=min(finalHeight[i],arr[j].first.second);}
               ~^~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 692 KB Output isn't correct
2 Halted 0 ms 0 KB -