oj.uz

Submission #725567

# Submission time Handle Problem Language Result Execution time Memory
725567 2023-04-17T16:37:44 Z allin27x Wall (IOI14_wall) C++14
32 / 100
 209 ms 20172 KB 
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;

struct SGT{
	int op;
	vector<int> t;
	int n;
	SGT(int sz, int op1){
		n= sz;
		op = op1;
		t.resize(2*n, (op==1)?0:(int)2e9);
	}
	void apply(int p, int x){
		t[p] = abs(max(op*t[p], op*x));
	}
	void update(int l, int r, int x){
		for (l+=n, r+=n+1; l<r; l>>=1, r>>=1){
			if (l&1) apply(l++, x);
			if (r&1) apply(--r, x);
		}
	}
	void push(){
		for (int i=1; i<n; i++){
			if (t[i]==-1) continue;
			apply(i<<1, t[i]);
			apply(i<<1|1, t[i]);
		}
	}
};

void brute_force(int n, int k, int op[], int l[],int r[],int h[], int ans[]){
	for (int i=0; i<k; i++){
		for(int j=l[i]; j<=r[i]; j++){
			if (op[i] == 1) ans[j] = max(ans[j] , h[i]);
			if (op[i] == 2) ans[j] = min(ans[j] , h[i]);
		} 
	}
}
void buildWall(int n, int k, int op[], int l[],int r[],int h[], int ans[]){
	if (n<=10000)  {brute_force(n,k,op,l,r,h, ans); return;}
	SGT add(n, 1);
	SGT rem(n, -1);
	for (int i=0; i<k; i++){
		if (op[i]==1) add.update(l[i], r[i], h[i]);
		if (op[i]==2) rem.update(l[i], r[i], h[i]);
	}
	add.push(); rem.push();
	for (int i=0; i<n; i++) ans[i] = min(add.t[i+n], rem.t[i+n]);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 22 ms 468 KB Output is correct
5 Correct 21 ms 408 KB Output is correct
6 Correct 22 ms 412 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 121 ms 8088 KB Output is correct
3 Correct 81 ms 3888 KB Output is correct
4 Correct 209 ms 10088 KB Output is correct
5 Correct 170 ms 17744 KB Output is correct
6 Correct 152 ms 17848 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 21 ms 400 KB Output is correct
5 Correct 21 ms 400 KB Output is correct
6 Correct 21 ms 396 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 121 ms 8152 KB Output is correct
9 Correct 82 ms 3808 KB Output is correct
10 Correct 204 ms 10052 KB Output is correct
11 Correct 161 ms 20172 KB Output is correct
12 Correct 157 ms 18688 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 129 ms 13900 KB Output is correct
15 Incorrect 14 ms 1620 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 21 ms 408 KB Output is correct
5 Correct 21 ms 412 KB Output is correct
6 Correct 21 ms 400 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 116 ms 8012 KB Output is correct
9 Correct 86 ms 3860 KB Output is correct
10 Correct 206 ms 9968 KB Output is correct
11 Correct 161 ms 20156 KB Output is correct
12 Correct 156 ms 18656 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 130 ms 13868 KB Output is correct
15 Incorrect 16 ms 1648 KB Output isn't correct
16 Halted 0 ms 0 KB -