| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 718699 |
2023-04-04T14:27:29 Z |
mseebacher |
Wall (IOI14_wall) |
C++17 |
|
2 ms |
2664 KB |
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define MAXI (int)1e5
#define pb(x) push_back(x)
#define inf 1e9+10
vector<int> ad[MAXI];
vector<bool> vis(MAXI,0);
void dfs(int x){
if(vis[x]) return;
vis[x] = 1;
for(auto s:ad[x]){
dfs(s);
}
}
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
int* dummy;
struct Node{
int mx;
int mn;
};
struct segtree{
int size = 0;
vector<Node> tree;
vector<bool> marked;
void init(int n){
int x = 1;
while(x < n) x*=2;
size = x;
Node a;
a.mx = inf;
a.mn = 0;
tree.assign(2*size,a);
marked.assign(2*size,0);
}
// x1 child, x2 parent
Node combine(Node u,Node p){
u.mx = max(u.mx,p.mn);
u.mx = min(u.mx,p.mx);
u.mn = max(p.mn,u.mn);
u.mn = min(u.mn,p.mx);
return u;
}
void push(int x){
tree[2*x] = combine(tree[2*x],tree[x]);
tree[2*x+1] = combine(tree[2*x+1],tree[x]);
marked[x] = 0;
marked[2*x] = marked[2*x+1] = 1;
tree[x].mx = inf;
tree[x].mn = 0;
}
void update(int op, int h,int l,int r,int x,int lx,int rx){
if(l > r) return;
if(l > rx || r < lx) return;
if(lx >= l && rx <= r){
if(op == 1){
tree[x].mn = max(tree[x].mn,h);
tree[x].mx = max(tree[x].mn,tree[x].mx);
}
else{
tree[x].mx = min(tree[x].mx,h);
tree[x].mn = min(tree[x].mn,tree[x].mx);
}
//cout << tree[x].mn << " " << tree[x].mx << "\n";
marked[x] = 1;
if(lx == rx){
dummy[l] = min(max(0,tree[x].mn),tree[x].mx);
}
return;
}
if(marked[x])push(x);
int m = (lx+rx) >> 1;
update(op,h,l,r,2*x,lx,m);
update(op,h,l,r,2*x+1,m+1,rx);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
segtree s;
s.init(4*n);
dummy = finalHeight;
for(int i = 0;i<k;i++){
s.update(op[i],height[i],left[i],right[i],1,0,s.size-1);
}
for(int i = 0;i<n;i++){
s.update(1,0,i,i,1,0,s.size-1);
}
for(int i = 0;i<n;i++){
cout << finalHeight[i] << " ";
}
}
Compilation message
wall.cpp: In function 'void setIO(std::string)':
wall.cpp:24:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
