| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 784001 |
2023-07-15T14:12:18 Z |
canadavid1 |
Wall (IOI14_wall) |
C++14 |
|
1 ms |
212 KB |
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define clamp(x,l,r) x=min(r,max(x,l))
#define all(x) begin(x),end(x)
struct Node
{
int ls=-1;
int when=-1;
int le,re;
Node *lc,*rc;
Node() {}
Node(int le, int re) : le(le), re(re) {}
Node(int le, int re,Node* lc, Node* rc) : le(le), re(re), lc(lc),rc(rc) {}
void set(int l, int r, int val,int time)
{
l = max(l,le);
r = min(r,re);
if(l>=r) return;
if(l==le && r==re) {ls = val;when=time;return;}
if(ls != -1)
{
if(lc) {lc->ls = ls;lc->when = when;}
if(rc) {rc->ls = ls;lc->when = when;}
ls = -1;
when = -1;
}
if(lc) lc->set(l,r,val,time);
if(rc) rc->set(l,r,val,time);
}
void propdown(vector<pair<int,int>>& out)
{
if(re - le <= 1)
{
out[le].first = ls;
out[le].second = when;
return;
}
if(ls != -1)
{
if(lc) {lc->ls = ls;lc->when = when;}
if(rc) {rc->ls = ls;lc->when = when;}
ls = -1;
when = -1;
}
if(lc) lc->propdown(out);
if(rc) rc->propdown(out);
}
void prn(string before="")
{
cout << /* object info*/ ls << " " << le << " " << re << "\n";
if(lc != nullptr || rc != nullptr)
{
cout << before << "+-";
before.append("| ");
if(lc == nullptr) cout << "nullptr\n";
else lc->prn(before);
before.pop_back();before.pop_back();
}
if(rc != nullptr)
{
cout << before << "'-";
before.append(" ");
if(rc == nullptr) cout << "nullptr\n";
else rc->prn(before);
before.pop_back();before.pop_back();
}
}
};
template<typename... args>
Node* newNode(args... a)
{
static Node* arr = nullptr;
static int count = 1024;
if(count >= 1024)
{
arr = new Node[1024];
count = 0;
}
arr[count].~Node();
return new(&arr[count++]) Node(a...);
}
Node* makeTree(int l, int r)
{
if (r-1 <= l) return newNode(l,r,nullptr,nullptr);
int m = (r+l)/2; // could be other heuristic
return newNode(l,r,makeTree(l,m),makeTree(m,r));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
// lazy update segment tree
Node* a = makeTree(0,n);
vector<tuple<int,int,int,int,int>> ops(k);
for(int i = 0; i < k; i++) ops[i] = {op[i],height[i],left[i],right[i],i};
sort(all(ops));
for(int i = 0; i < k && get<0>(ops[i]) != 2; i++)
{
auto[p,h,l,r,time] = ops[i];
a->set(l,r,h,time);
}
vector<pair<int,int>> minima(n);
a->propdown(minima);
a->set(0,n,INT_MAX,-1);
for(int i = k-1; i >= 0 && get<0>(ops[i]) != 1; --i)
{
auto[p,h,l,r,time] = ops[i];
a->set(l,r,h,time);
}
vector<pair<int,int>> maxima(n);
a->propdown(maxima);
for(int i = 0; i < n; i++)
{
// assuming minima happen before maxima
finalHeight[i] = min(minima[i].first,maxima[i].first);
}
return;
}
Compilation message
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:107:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
107 | auto[p,h,l,r,time] = ops[i];
| ^
wall.cpp:115:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
115 | auto[p,h,l,r,time] = ops[i];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
