oj.uz

Submission #1100795

# Submission time Handle Problem Language Result Execution time Memory
1100795 2024-10-14T18:20:52 Z Dan4Life Wall (IOI14_wall) C++17
0 / 100
 490 ms 13136 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int mxN = (int)2e6+10;
const int INF = (int)1e9;
 
int n, q, x[mxN];
array<int,2> seg[mxN*2], Init={INF,-INF};
 
void prop(int p, int l, int r){
    if(l==r or seg[p]==Init) return;
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    auto [a,b] = seg[p];
    seg[p+1][0] = min(a, max(seg[p+1][0], b));
    seg[p+1][1] = max(seg[p+1][1], b);
    seg[rp][0] = min(a, max(seg[rp][0], b));
    seg[rp][1] = max(seg[rp][1], b);
    seg[p] = Init;
}
 
void upd(int i, int j, int a, int b, int p=0, int l=0, int r=n-1){
    if(i>j or i>r or j<l) return; prop(p,l,r);
    if(i<=l and r<=j){
        seg[p][0] = min(a, max(seg[p][0], b));
        seg[p][1] = max(seg[p][1], b);
        return;
    }
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    upd(i,j,a,b,p+1,l,mid); upd(i,j,a,b,rp,mid+1,r);
}
 
int query(int i, int p=0, int l=0, int r=n-1){
    if(l==r) return min(seg[p][0],max(x[l],seg[p][1]));
    prop(p,l,r);
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    if(i<=mid) return query(i,p+1,l,mid);
    return query(i,rp,mid+1,r);
}
 
void buildWall(int N, int k, int o[], int l[], int r[], int h[], int ans[]){
    n = N; fill(seg,seg+2*n,Init);
    for(int i = 0; i < n; i++) x[i]=h[i], upd(i,i,INF,h[i]);
    for(int i = 0; i < k; i++){
		int a, b;
		if(o[i]==1) a = INF, b = h[i];
		else a = h[i], b = -INF;
		upd(l[i],r[i],a,b);
	}
    for(int i = 0; i < n; i++) ans[i] = query(i);
}

Compilation message

wall.cpp: In function 'void upd(int, int, int, int, int, int, int)':
wall.cpp:22:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   22 |     if(i>j or i>r or j<l) return; prop(p,l,r);
      |     ^~
wall.cpp:22:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   22 |     if(i>j or i>r or j<l) return; prop(p,l,r);
      |                                   ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 2 ms 2576 KB Output is correct
3 Correct 2 ms 2384 KB Output is correct
4 Incorrect 8 ms 2640 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 93 ms 10096 KB Output is correct
3 Correct 170 ms 7948 KB Output is correct
4 Incorrect 490 ms 13136 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 2 ms 2384 KB Output is correct
3 Correct 2 ms 2384 KB Output is correct
4 Incorrect 8 ms 2640 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 2 ms 2484 KB Output is correct
3 Correct 2 ms 2384 KB Output is correct
4 Incorrect 8 ms 2640 KB Output isn't correct
5 Halted 0 ms 0 KB -