oj.uz

Submission #986361

# Submission time Handle Problem Language Result Execution time Memory
986361 2024-05-20T11:17:15 Z Pyqe Wall (IOI14_wall) C++17
100 / 100
 789 ms 232496 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

int sq[2000069],inf=1e9;

struct segtree
{
	int l,r,lz[2];
	segtree *p[2];
	
	void bd(int lh,int rh)
	{
		int ii;
		
		l=lh;
		r=rh;
		lz[0]=-inf;
		lz[1]=inf;
		if(l==r)
		{
			for(ii=0;ii<2;ii++)
			{
				lz[ii]=0;
			}
		}
		else
		{
			int md=(l+r)/2;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
		}
	}
	void ad(int ky,int w)
	{
		int ii,u=!ky*2-1;
		
		for(ii=0;ii<2;ii++)
		{
			lz[ii]=max(lz[ii]*u,w*u)*u;
		}
	}
	void blc()
	{
		int ii,iii;
		
		for(ii=0;ii<2;ii++)
		{
			for(iii=0;iii<2;iii++)
			{
				p[ii]->ad(iii,lz[iii]);
			}
		}
		lz[0]=-inf;
		lz[1]=inf;
	}
	void ud(int ky,int lh,int rh,int w)
	{
		if(l>rh||r<lh);
		else if(l>=lh&&r<=rh)
		{
			ad(ky,w);
		}
		else
		{
			int ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ud(ky,lh,rh,w);
			}
		}
	}
	void trv()
	{
		if(l==r)
		{
			sq[l]=lz[0];
		}
		else
		{
			int ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->trv();
			}
		}
	}
}
sg;

void buildWall(int n,int t,int kya[],int la[],int ra[],int wg[],int sqq[])
{
	int rr,i;
	
	sg.bd(0,n-1);
	for(rr=0;rr<t;rr++)
	{
		sg.ud(kya[rr]-1,la[rr],ra[rr],wg[rr]);
	}
	sg.trv();
	for(i=0;i<n;i++)
	{
		sqq[i]=sq[i];
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1624 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 5 ms 1628 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 108 ms 14024 KB Output is correct
3 Correct 185 ms 8112 KB Output is correct
4 Correct 432 ms 30032 KB Output is correct
5 Correct 229 ms 31392 KB Output is correct
6 Correct 225 ms 29404 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1628 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 4 ms 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 112 ms 13836 KB Output is correct
9 Correct 141 ms 9360 KB Output is correct
10 Correct 427 ms 29932 KB Output is correct
11 Correct 222 ms 30924 KB Output is correct
12 Correct 226 ms 29356 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 109 ms 13904 KB Output is correct
15 Correct 24 ms 3164 KB Output is correct
16 Correct 409 ms 30144 KB Output is correct
17 Correct 220 ms 29640 KB Output is correct
18 Correct 218 ms 29704 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1668 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 7 ms 1476 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 111 ms 13932 KB Output is correct
9 Correct 167 ms 9232 KB Output is correct
10 Correct 453 ms 30088 KB Output is correct
11 Correct 225 ms 30892 KB Output is correct
12 Correct 230 ms 29332 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 109 ms 14068 KB Output is correct
15 Correct 27 ms 3116 KB Output is correct
16 Correct 470 ms 30348 KB Output is correct
17 Correct 238 ms 29524 KB Output is correct
18 Correct 228 ms 29644 KB Output is correct
19 Correct 749 ms 232348 KB Output is correct
20 Correct 705 ms 229872 KB Output is correct
21 Correct 710 ms 232496 KB Output is correct
22 Correct 699 ms 229812 KB Output is correct
23 Correct 789 ms 229780 KB Output is correct
24 Correct 761 ms 229772 KB Output is correct
25 Correct 731 ms 229940 KB Output is correct
26 Correct 754 ms 232324 KB Output is correct
27 Correct 720 ms 232292 KB Output is correct
28 Correct 730 ms 229800 KB Output is correct
29 Correct 721 ms 229788 KB Output is correct
30 Correct 747 ms 229768 KB Output is correct