oj.uz

Submission #901981

# Submission time Handle Problem Language Result Execution time Memory
901981 2024-01-10T05:10:32 Z MuhammadSaram Wall (IOI14_wall) C++17
61 / 100
 3000 ms 248448 KB 
#include <bits/stdc++.h>

using namespace std;

const int M = 5e5, inf = 1e6;

int seg[2][M*4],k;

void modify(int ty,int p,int x,int v=1,int s=0,int e=k)
{
	if (s+1==e)
	{
		seg[ty][v]=x;
		return;
	}
	int mid=(s+e)/2,lc=v*2,rc=v*2+1;
	if (p<mid)
		modify(ty,p,x,lc,s,mid);
	else
		modify(ty,p,x,rc,mid,e);
	if (ty)
		seg[ty][v]=min(seg[ty][lc],seg[ty][rc]);
	else
		seg[ty][v]=max(seg[ty][lc],seg[ty][rc]);
}

int get(int ty,int l,int r,int v=1,int s=0,int e=k)
{
	if (r<=s or e<=l)
		return ty*inf;
	if (l<=s and e<=r)
		return seg[ty][v];
	int mid=(s+e)/2,lc=v*2,rc=v*2+1;
	if (ty)
		return min(get(ty,l,r,lc,s,mid),get(ty,l,r,rc,mid,e));
	return max(get(ty,l,r,lc,s,mid),get(ty,l,r,rc,mid,e));
}

void buildWall(int n, int K, int op[], int left[], int right[], int height[], int finalHeight[])
{
	k=K;
	for (int i=0;i<k;i++)
		for (int j=0;j<2;j++)
			modify(j,i,j*inf);
	vector<pair<int,int>> st[2][n],en[2][n];
	for (int i=0;i<k;i++)
	{
		st[op[i]-1][left[i]].push_back({i,height[i]});
		en[op[i]-1][right[i]].push_back({i,height[i]});
	}
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<2;j++)
			for (auto x:st[j][i])
				modify(j,x.first,x.second);
		int s=-1,e=k;
		while (s+1<e)
		{
			int mid=(s+e)/2;
			int x=get(0,mid,k),y=get(1,mid,k);
			if (x>y)
				s=mid;
			else
				e=mid;
		}
		if (s==-1)
			finalHeight[i]=get(0,0,k);
		else
		{
			int x=get(0,s,k),y=get(1,s,k);
			int x1=get(0,s+1,k),y1=get(1,s+1,k);
			if (x==x1)
				finalHeight[i]=x;
			else
				finalHeight[i]=y;
		}
		for (int j=0;j<2;j++)
			for (auto x:en[j][i])
				modify(j,x.first,inf*j);
	}
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:71:24: warning: unused variable 'y1' [-Wunused-variable]
   71 |    int x1=get(0,s+1,k),y1=get(1,s+1,k);
      |                        ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 3 ms 2756 KB Output is correct
3 Correct 3 ms 2648 KB Output is correct
4 Correct 28 ms 4184 KB Output is correct
5 Correct 27 ms 4184 KB Output is correct
6 Correct 27 ms 3932 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 332 ms 33556 KB Output is correct
3 Correct 217 ms 21072 KB Output is correct
4 Correct 1014 ms 54352 KB Output is correct
5 Correct 775 ms 50644 KB Output is correct
6 Correct 756 ms 49572 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 22 ms 3932 KB Output is correct
5 Correct 26 ms 3932 KB Output is correct
6 Correct 30 ms 3932 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 335 ms 34300 KB Output is correct
9 Correct 211 ms 20992 KB Output is correct
10 Correct 962 ms 54472 KB Output is correct
11 Correct 802 ms 50612 KB Output is correct
12 Correct 763 ms 49332 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 335 ms 32384 KB Output is correct
15 Correct 59 ms 8668 KB Output is correct
16 Correct 965 ms 54492 KB Output is correct
17 Correct 853 ms 49936 KB Output is correct
18 Correct 849 ms 50008 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 4 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 22 ms 3928 KB Output is correct
5 Correct 26 ms 3940 KB Output is correct
6 Correct 26 ms 3932 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 334 ms 34708 KB Output is correct
9 Correct 209 ms 21040 KB Output is correct
10 Correct 1043 ms 54228 KB Output is correct
11 Correct 754 ms 50884 KB Output is correct
12 Correct 762 ms 49320 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 379 ms 32416 KB Output is correct
15 Correct 59 ms 8684 KB Output is correct
16 Correct 968 ms 54504 KB Output is correct
17 Correct 919 ms 50032 KB Output is correct
18 Correct 865 ms 49988 KB Output is correct
19 Execution timed out 3050 ms 248448 KB Time limit exceeded
20 Halted 0 ms 0 KB -