oj.uz

Submission #62453

# Submission time Handle Problem Language Result Execution time Memory
62453 2018-07-28T13:56:06 Z evpipis Wall (IOI14_wall) C++11
61 / 100
 1266 ms 209480 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

//#define TEST

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;

const int len = 1e5+5, inf = 1e9;
ii tree[4*len];

void upd(ii &a, ii b){
    if (a.fi <= b.fi && b.se <= a.se)
        a = b;
    else if (b.fi < a.fi)
        a.se = min(a.se, b.se), a.fi = min(a.fi, b.se);
    else if (b.se > a.se)
        a.fi = max(a.fi, b.fi), a.se = max(a.se, b.fi);
}

void prop(int p, int l, int r){
    if (l == r) return;

    upd(tree[2*p], tree[p]);
    upd(tree[2*p+1], tree[p]);
    tree[p] = mp(0, inf);
}

void update(int p, int l, int r, int i, int j, ii val){
    prop(p, l, r);
    if (r < i || j < l)
        return;
    if (i <= l && r <= j)
        upd(tree[p], val);
    else{
        int mid = (l+r)/2;
        update(2*p, l, mid, i, j, val);
        update(2*p+1, mid+1, r, i, j, val);
    }
}

int query(int p, int l, int r, int i){
    prop(p, l, r);
    if (l == r)
        return tree[p].fi;

    int mid = (l+r)/2;
    if (i <= mid)
        return query(2*p, l, mid, i);
    return query(2*p+1, mid+1, r, i);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < 4*n; i++)
        tree[i] = mp(0, inf);

    for (int i = 0; i < k; i++){
        ii val;
        int t = op[i], l = left[i], r = right[i], h = height[i];
        if (t == 1)
            val = mp(h, inf);
        else
            val = mp(0, h);

        update(1, 0, n-1, l, r, val);
    }

    for (int i = 0; i < n; i++)
        finalHeight[i] = query(1, 0, n-1, i);
    return;
}

#ifdef TEST
int main()
{
  int n;
  int k;

  int i, j;
  int status = 0;

  status = scanf("%d%d", &n, &k);
  assert(status == 2);

  int* op = (int*)calloc(sizeof(int), k);
  int* left = (int*)calloc(sizeof(int), k);
  int* right = (int*)calloc(sizeof(int), k);
  int* height = (int*)calloc(sizeof(int), k);
  int* finalHeight = (int*)calloc(sizeof(int), n);

  for (i = 0; i < k; i++){
    status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
    assert(status == 4);
  }

  buildWall(n, k, op, left, right, height, finalHeight);

  for (j = 0; j < n; j++)
    printf("%d\n", finalHeight[j]);

  return 0;
}
#endif

/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 248 KB Output is correct
2 Correct 5 ms 488 KB Output is correct
3 Correct 4 ms 656 KB Output is correct
4 Correct 15 ms 1256 KB Output is correct
5 Correct 11 ms 1296 KB Output is correct
6 Correct 10 ms 1396 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1396 KB Output is correct
2 Correct 238 ms 14656 KB Output is correct
3 Correct 351 ms 14704 KB Output is correct
4 Correct 977 ms 31924 KB Output is correct
5 Correct 620 ms 42640 KB Output is correct
6 Correct 511 ms 51272 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 51272 KB Output is correct
2 Correct 6 ms 51272 KB Output is correct
3 Correct 6 ms 51272 KB Output is correct
4 Correct 18 ms 51272 KB Output is correct
5 Correct 10 ms 51272 KB Output is correct
6 Correct 10 ms 51272 KB Output is correct
7 Correct 2 ms 51272 KB Output is correct
8 Correct 217 ms 53072 KB Output is correct
9 Correct 298 ms 53072 KB Output is correct
10 Correct 980 ms 70356 KB Output is correct
11 Correct 523 ms 80968 KB Output is correct
12 Correct 471 ms 89632 KB Output is correct
13 Correct 3 ms 89632 KB Output is correct
14 Correct 223 ms 91232 KB Output is correct
15 Correct 57 ms 91232 KB Output is correct
16 Correct 1044 ms 105336 KB Output is correct
17 Correct 466 ms 114408 KB Output is correct
18 Correct 563 ms 123308 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 123308 KB Output is correct
2 Correct 5 ms 123308 KB Output is correct
3 Correct 6 ms 123308 KB Output is correct
4 Correct 14 ms 123308 KB Output is correct
5 Correct 12 ms 123308 KB Output is correct
6 Correct 12 ms 123308 KB Output is correct
7 Correct 3 ms 123308 KB Output is correct
8 Correct 229 ms 125852 KB Output is correct
9 Correct 332 ms 125852 KB Output is correct
10 Correct 944 ms 143068 KB Output is correct
11 Correct 474 ms 153392 KB Output is correct
12 Correct 437 ms 160760 KB Output is correct
13 Correct 3 ms 160760 KB Output is correct
14 Correct 231 ms 161736 KB Output is correct
15 Correct 59 ms 161736 KB Output is correct
16 Correct 1266 ms 175704 KB Output is correct
17 Correct 589 ms 182620 KB Output is correct
18 Correct 501 ms 190796 KB Output is correct
19 Runtime error 278 ms 209480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -