oj.uz

Submission #1026963

# Submission time Handle Problem Language Result Execution time Memory
1026963 2024-07-18T15:25:15 Z socpite Wall (IOI14_wall) C++17
0 / 100
 407 ms 107816 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e6+5;
const int mxval = 1e5;

struct phase{
	int ty, h, id;
	phase(int _ty, int _h, int _id): ty(_ty), h(_h), id(_id){};
};
vector<phase> vec[maxn];

set<int> mx[mxval + 5][2];

int st[4*mxval + 20][2];

void edit(int ty, int pos, int l = 0, int r = mxval, int id = 1){
	if(l == r)st[id][ty] = (mx[l][ty].empty() ? 0 : *mx[l][ty].rend());
	else {
		int mid = (l+r)>>1;
		if(pos <= mid)edit(ty, pos, l, mid, id<<1);
		else edit(ty, pos, mid+1, r, id<<1|1);
		st[id][ty] = max(st[id<<1][ty], st[id<<1|1][ty]);
	}
}

int query(int lmax = 1, int rmax = 0, int l = 0, int r = mxval, int id = 1){
	if(l == r)return l;
	else {
		int mid = (l+r)>>1;
		if(max(st[id<<1][1], lmax) > max(st[id<<1|1][0], rmax))return query(lmax, max(st[id<<1|1][0], rmax), l, mid, id<<1);
		else return query(max(st[id<<1][1], lmax), rmax, mid+1, r, id<<1|1);
	}
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = 0; i < k; i++){
		vec[left[i]].push_back(phase(op[i]-1, height[i], i+2));
		vec[right[i] + 1].push_back(phase(op[i]-1, height[i], i+2));
	}
	for(int i = 0; i < n; i++){
		for(auto v: vec[i]){
			if(mx[v.h][v.ty].find(v.id) != mx[v.h][v.ty].end())mx[v.h][v.ty].erase(v.id);
			else mx[v.h][v.ty].insert(v.id);
			edit(v.ty, v.h);
		}
		finalHeight[i] = query();
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 59736 KB Output is correct
2 Correct 12 ms 60396 KB Output is correct
3 Correct 11 ms 59996 KB Output is correct
4 Correct 15 ms 60352 KB Output is correct
5 Incorrect 13 ms 59228 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 59740 KB Output is correct
2 Correct 275 ms 107816 KB Output is correct
3 Correct 144 ms 78388 KB Output is correct
4 Incorrect 407 ms 106064 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 59736 KB Output is correct
2 Correct 12 ms 60380 KB Output is correct
3 Correct 12 ms 60064 KB Output is correct
4 Correct 14 ms 60504 KB Output is correct
5 Incorrect 14 ms 59228 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 59728 KB Output is correct
2 Correct 12 ms 60404 KB Output is correct
3 Correct 11 ms 59996 KB Output is correct
4 Correct 14 ms 60460 KB Output is correct
5 Incorrect 16 ms 59224 KB Output isn't correct
6 Halted 0 ms 0 KB -