| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 291134 |
2020-09-04T18:18:44 Z |
ivan24 |
Wall (IOI14_wall) |
C++14 |
|
167 ms |
10744 KB |
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second
const ll INF = 1e9;
class SegmentTree {
private:
vi st, data;
vii lzy;
ll n;
ll left(ll x){ return (x << 1); }
ll right(ll x) { return ((x << 1) + 1); }
ii cmbNodes(ii lhs, ii rhs){
ii ans = ii(max(lhs.F,rhs.F),min(lhs.S,rhs.S));
if (ans.F <= ans.S) return ans;
if (lhs.S < rhs.F) ans.F = lhs.S;
else ans.S = lhs.F;
}
void rangeUpdate (ll i, ll l, ll r, ll ul, ll ur, ii newNode){
//cout << i << " " << l << " " << r << " " << ul << " " << ur << " " << endl;
if (l != r){
lzy[left(i)] = cmbNodes(lzy[i],lzy[left(i)]);
lzy[right(i)] = cmbNodes(lzy[i],lzy[right(i)]);
lzy[i] = ii(0,INF);
}
if (ur >= r && l >= ul){
lzy[i] = cmbNodes(newNode,lzy[i]);
}else if (max(ul,l) <= min(ur,r)){
ll m = (l+r)/2;
rangeUpdate(left(i),l,m,ul,ur,newNode);
rangeUpdate(right(i),m+1,r,ul,ur,newNode);
}
}
ii query (ll i, ll l, ll r, ll idx){
if (r >= idx && idx >= l){
ii ans = lzy[i];
ll m = (l+r)/2;
if (l != r){
ii lans = query(left(i),l,m,idx);
ii rans = query(right(i),m+1,r,idx);
ans = cmbNodes(ans,lans);
ans = cmbNodes(ans,rans);
}
return ans;
}else{
return ii(0,INF);
}
}
void printLzy(ll i, ll l, ll r){
cout << i << " " << l << "-" << r << " : " << lzy[i].F << " , " << lzy[i].S << endl;
if (l != r){
ll m = (l+r)/2;
printLzy(left(i),l,m);
printLzy(right(i),m+1,r);
}
}
void build (ll i, ll l, ll r){
if (l == r){
lzy[i] = ii(0,0);
}else{
lzy[i] = ii(0,INF);
ll m = (l+r)/2;
build(left(i),l,m);
build(right(i),m+1,r);
}
}
public:
SegmentTree (ll sz): st(sz*4), data(sz), lzy(sz*4,ii(0,0)), n(sz){
build(1,0,n-1);
}
void update (ll l, ll r, ii newNode){
rangeUpdate(1,0,n-1,l,r,newNode);
}
ll query (ll idx){
ii ans = query(1,0,n-1,idx);
//cout << ans.F << " " << ans.S << endl;
return ans.F;
}
vi get_all_data(){
vi ans(n);
for (ll i = 0; n > i; i++) ans[i] = query(i);
return ans;
}
void print(){
printLzy(1,0,n-1);
}
void print_data(){
vi res = get_all_data();
for (auto i: res) cout << i << " ";
cout << endl;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SegmentTree st(n);
for (ll i = 0; k > i; i++){
//cout << i << endl;
ii newNode = ii(0,INF);
if (op[i] == 1) newNode.F = height[i];
else newNode.S = height[i];
st.update(left[i],right[i],newNode);
//st.print_data();
//st.print();
}
//st.print();
vi res = st.get_all_data();
for (ll i = 0; n > i; i++) finalHeight[i] = abs(res[i]);
}
Compilation message
wall.cpp: In member function 'ii SegmentTree::cmbNodes(ii, ii)':
wall.cpp:28:5: warning: control reaches end of non-void function [-Wreturn-type]
28 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
167 ms |
10744 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
