| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1039209 |
2024-07-30T14:33:04 Z |
mateuszwes |
Wall (IOI14_wall) |
C++17 |
|
16 ms |
33352 KB |
#include "wall.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define F first
#define S second
#define pb push_back
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pq priority_queue
using namespace std;
constexpr int debug = 1;
constexpr int N = 2e6+7;
constexpr int M = 1e5+7;
constexpr int base = 1<<21;
int l, r;
pi tree[2*base+7], tree2[2*base+7]; //min, maks
//if new min smaller then keep unchanged
//if new min > old min then adjust min
//if new min > max then max = min
//etc
//these changes are ok because they include the time
void mini(int git, int v){
if(git == -1) return;
if(git > tree[v].F){
tree[v].F = tree2[v].F = git;
if(git > tree[v].S){
tree[v].S = tree2[v].S = git;
}
}
}
void maxi(int git, int v){
if(git == -1) return;
if(git < tree[v].S){
tree[v].S = tree2[v].S = git;
if(git < tree[v].F){
tree[v].S = tree2[v].S = git;
}
}
}
void push(int v){
mini(tree2[v].F, 2*v);
maxi(tree2[v].F, 2*v);
mini(tree2[v].S, 2*v+1);
maxi(tree2[v].S, 2*v+1);
tree2[v] = {-1, -1};
}
void change(int v, int operation, int val, int a, int b){
if((b < l) || (a > r)) return;
else if((a >= l) && (b <= r)){
if(operation == 1){
mini(val, v);
}
else{
maxi(val, v);
}
}
else{
int mid = (a+b)/2;
push(v);
change(2*v, operation, val, a, mid);
change(2*v+1, operation, val, mid+1, b);
tree[v] = {min(tree[2*v].F, tree[2*v+1].F), max(tree[2*v].S, tree[2*v+1].S)};
}
}
int read(int i, int v, int a, int b){
if((b < i) || (a > i)) return -1;
else if((a >= i) && (b <= i)){
return tree[v].F;
}
else{
int mid = (a+b)/2;
push(v);
int sc = read(i, 2*v, a, mid);
if(sc == -1) return read(i, 2*v+1, mid+1, b);
return sc;
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
fill(finalHeight, finalHeight+n, 0);
for(int i = 0; i < 2*base+7; i++) tree2[i] = {-1, -1};
//1 is for adding
for(int i = 0; i < k; i++){
l = left[i];
r = right[i];
change(1, op[i], height[i], 0, base-1);
}
for(int i = 0; i < n; i++){
finalHeight[i] = read(i, 1, 0, base-1);
if(debug) cout << finalHeight[i] << '\n';
}
}
/*
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int ok[] = {1, 2, 2, 1, 1, 2};
int lel[] = {1, 4, 3, 0, 2, 6};
int rer[] = {8, 9, 6, 5, 2, 7};
int heh[] = {4, 1 ,5, 3, 5 ,0};
int fif[] = {0, 0, 0, 0, 0, 0};
buildWall(10, 6, ok[], lel[], rer[], heh[], fif[]);
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
33112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
33116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
33352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
33116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
