oj.uz

답안 #425303

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
425303 2021-06-12T20:14:01 Z MarcoMeijer 벽 (IOI14_wall) C++14
100 / 100
 1495 ms 69604 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<ii> vii;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), e.end()

const int MX = 1e5;
const int N = (1<<21);

int seglb[N*2], segub[N*2];
void buildSeg(int p=1, int l=0, int r=N-1) {
  seglb[p] = 0;
  segub[p] = 0;
  if(l == r) return;
  int m=(l+r)/2;
  buildSeg(p*2,l,m);
  buildSeg(p*2+1,m+1,r);
}
void applyRegion(int p, int lb, int ub) {
  seglb[p] = min(seglb[p], ub);
  segub[p] = min(segub[p], ub);
  seglb[p] = max(seglb[p], lb);
  segub[p] = max(segub[p], lb);
}
void pushSeg(int p) {
  applyRegion(p*2,seglb[p],segub[p]);
  applyRegion(p*2+1,seglb[p],segub[p]);
  seglb[p] = 0;
  segub[p] = 1e9;
}
void addSeg(int i, int j, int lb, int ub, int p=1, int l=0, int r=N-1) {
  if(j < l || i > r) return;
  if(i <= l && j >= r) {
    applyRegion(p,lb,ub);
    return;
  }
  pushSeg(p);
  int m=(l+r)/2;
  addSeg(i,j,lb,ub,p*2,l,m);
  addSeg(i,j,lb,ub,p*2+1,m+1,r);
}
int getSeg(int i, int p=1, int l=0, int r=N-1) {
  if(i < l || i > r) return 0;
  if(l == r) return seglb[p];
  pushSeg(p);
  int m=(l+r)/2;
  int a=getSeg(i,p*2,l,m);
  int b=getSeg(i,p*2+1,m+1,r);
  return a+b;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  buildSeg();
  RE(i,k) {
    if(op[i] == 1) {
      addSeg(left[i], right[i], height[i], 1e9);
    } else {
      addSeg(left[i], right[i], 0, height[i]);
    }
  }
  RE(i,n) finalHeight[i] = getSeg(i);
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 33092 KB Output is correct
2 Correct 31 ms 33144 KB Output is correct
3 Correct 29 ms 33184 KB Output is correct
4 Correct 41 ms 33208 KB Output is correct
5 Correct 36 ms 33228 KB Output is correct
6 Correct 35 ms 33216 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 33040 KB Output is correct
2 Correct 429 ms 40948 KB Output is correct
3 Correct 250 ms 36420 KB Output is correct
4 Correct 651 ms 41464 KB Output is correct
5 Correct 459 ms 41980 KB Output is correct
6 Correct 450 ms 42144 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 33020 KB Output is correct
2 Correct 31 ms 33096 KB Output is correct
3 Correct 29 ms 33108 KB Output is correct
4 Correct 40 ms 33356 KB Output is correct
5 Correct 35 ms 33232 KB Output is correct
6 Correct 35 ms 33228 KB Output is correct
7 Correct 27 ms 33048 KB Output is correct
8 Correct 394 ms 40940 KB Output is correct
9 Correct 259 ms 36424 KB Output is correct
10 Correct 641 ms 41440 KB Output is correct
11 Correct 452 ms 42016 KB Output is correct
12 Correct 444 ms 42056 KB Output is correct
13 Correct 29 ms 33092 KB Output is correct
14 Correct 427 ms 40904 KB Output is correct
15 Correct 68 ms 33732 KB Output is correct
16 Correct 672 ms 41724 KB Output is correct
17 Correct 517 ms 41724 KB Output is correct
18 Correct 473 ms 41724 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 33088 KB Output is correct
2 Correct 31 ms 33176 KB Output is correct
3 Correct 29 ms 33100 KB Output is correct
4 Correct 36 ms 33204 KB Output is correct
5 Correct 37 ms 33228 KB Output is correct
6 Correct 36 ms 33212 KB Output is correct
7 Correct 27 ms 33092 KB Output is correct
8 Correct 408 ms 41056 KB Output is correct
9 Correct 256 ms 36428 KB Output is correct
10 Correct 665 ms 41464 KB Output is correct
11 Correct 522 ms 41924 KB Output is correct
12 Correct 452 ms 41924 KB Output is correct
13 Correct 30 ms 33224 KB Output is correct
14 Correct 436 ms 41024 KB Output is correct
15 Correct 67 ms 33732 KB Output is correct
16 Correct 717 ms 41740 KB Output is correct
17 Correct 471 ms 41684 KB Output is correct
18 Correct 444 ms 41720 KB Output is correct
19 Correct 1467 ms 59020 KB Output is correct
20 Correct 1472 ms 66984 KB Output is correct
21 Correct 1457 ms 69604 KB Output is correct
22 Correct 1495 ms 66988 KB Output is correct
23 Correct 1459 ms 67004 KB Output is correct
24 Correct 1451 ms 67008 KB Output is correct
25 Correct 1455 ms 67092 KB Output is correct
26 Correct 1466 ms 69480 KB Output is correct
27 Correct 1471 ms 69500 KB Output is correct
28 Correct 1466 ms 67012 KB Output is correct
29 Correct 1458 ms 66908 KB Output is correct
30 Correct 1456 ms 67012 KB Output is correct