| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 276964 |
2020-08-20T21:54:07 Z |
mat_v |
벽 (IOI14_wall) |
C++14 |
|
0 ms |
384 KB |
#include "wall.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define maxn 2000005
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int lazy[4 * maxn][2];
int seg[4 * maxn];
int niz[maxn];
bool treba[4 * maxn];
void propagate(int node, int l, int r){
if(lazy[node][0]){
int val = lazy[node][0];
lazy[node * 2][0] = max(lazy[node * 2][0], val);
seg[node * 2] = max(seg[node * 2], lazy[node * 2][0]);
lazy[node * 2 + 1][0] = max(lazy[node * 2 + 1][0], val);
seg[node * 2 + 1] = max(seg[node * 2 + 1], lazy[node * 2 + 1][0]);
lazy[node][0] = 0;
}
if(lazy[node][1] < 1e9){
int val = lazy[node][1];
lazy[node * 2][1] = min(lazy[node * 2][1], val);
seg[node * 2] = min(seg[node * 2], lazy[node * 2][1]);
lazy[node * 2 + 1][1] = min(lazy[node * 2 + 1][1], val);
seg[node * 2 + 1] = min(seg[node * 2 + 1], lazy[node * 2 + 1][1]);
lazy[node][1] = 1e9;
}
}
void apdejt(int node, int l, int r, int levo, int desno, int h, int idx){
propagate(node, l, r);
if(r < levo || l > desno)return;
if(l >= levo && r <= desno){
if(idx == 0){
if(lazy[node][0] >= h)return;
seg[node] = max(seg[node], h);
lazy[node][0] = h;
if(lazy[node][1] < lazy[node][0])lazy[node][1] = h;
}
else{
if(lazy[node][1] <= h)return;
seg[node] = min(seg[node], h);
lazy[node][1] = h;
if(lazy[node][1] < lazy[node][0])lazy[node][0] = h;
}
propagate(node, l, r);
return;
}
propagate(node, l, r);
int mid = (l + r) / 2;
apdejt(node * 2, l, mid, levo, desno, h, idx);
apdejt(node * 2 + 1, mid + 1, r, levo, desno, h, idx);
}
int query(int node, int l, int r, int poz){
propagate(node, l, r);
if(l == r)return seg[node];
int mid = (l + r) / 2;
if(poz <= mid)return query(node * 2, l, mid, poz);
return query(node * 2 + 1, mid + 1, r, poz);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
ff(i,0,4 * n){
lazy[i][0] = 0;
lazy[i][1] = 1e9;
seg[i] = 1;
}
ff(i,0,k - 1){
int idx = op[i] - 1;
int l = left[i] + 1;
int r = right[i] + 1;
int h = height[i] + 1;
apdejt(1,1,n,l,r,h,idx|1);
}
ff(i,0,n - 1)finalHeight[i] = max(query(1,1,n,i+1) - 1,0);
}
Compilation message
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
8 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
wall.cpp:87:5: note: in expansion of macro 'ff'
87 | ff(i,0,4 * n){
| ^~
wall.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
8 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
wall.cpp:92:5: note: in expansion of macro 'ff'
92 | ff(i,0,k - 1){
| ^~
wall.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
8 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
wall.cpp:99:5: note: in expansion of macro 'ff'
99 | ff(i,0,n - 1)finalHeight[i] = max(query(1,1,n,i+1) - 1,0);
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
