oj.uz

Submission #62454

# Submission time Handle Problem Language Result Execution time Memory
62454 2018-07-28T13:57:05 Z evpipis Wall (IOI14_wall) C++11
100 / 100
 1783 ms 205276 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 = 2e6, 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 3 ms 376 KB Output is correct
2 Correct 6 ms 536 KB Output is correct
3 Correct 7 ms 588 KB Output is correct
4 Correct 15 ms 1156 KB Output is correct
5 Correct 15 ms 1156 KB Output is correct
6 Correct 12 ms 1356 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1356 KB Output is correct
2 Correct 220 ms 14508 KB Output is correct
3 Correct 403 ms 14508 KB Output is correct
4 Correct 944 ms 20916 KB Output is correct
5 Correct 631 ms 21440 KB Output is correct
6 Correct 548 ms 21552 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 21552 KB Output is correct
2 Correct 3 ms 21552 KB Output is correct
3 Correct 6 ms 21552 KB Output is correct
4 Correct 13 ms 21552 KB Output is correct
5 Correct 14 ms 21552 KB Output is correct
6 Correct 17 ms 21552 KB Output is correct
7 Correct 2 ms 21552 KB Output is correct
8 Correct 181 ms 21552 KB Output is correct
9 Correct 358 ms 21552 KB Output is correct
10 Correct 1096 ms 21552 KB Output is correct
11 Correct 584 ms 21552 KB Output is correct
12 Correct 688 ms 21636 KB Output is correct
13 Correct 3 ms 21636 KB Output is correct
14 Correct 259 ms 21636 KB Output is correct
15 Correct 64 ms 21636 KB Output is correct
16 Correct 1291 ms 21636 KB Output is correct
17 Correct 535 ms 21636 KB Output is correct
18 Correct 604 ms 21636 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21636 KB Output is correct
2 Correct 5 ms 21636 KB Output is correct
3 Correct 5 ms 21636 KB Output is correct
4 Correct 14 ms 21636 KB Output is correct
5 Correct 12 ms 21636 KB Output is correct
6 Correct 16 ms 21636 KB Output is correct
7 Correct 3 ms 21636 KB Output is correct
8 Correct 220 ms 21636 KB Output is correct
9 Correct 351 ms 21636 KB Output is correct
10 Correct 1034 ms 21636 KB Output is correct
11 Correct 523 ms 21636 KB Output is correct
12 Correct 500 ms 21636 KB Output is correct
13 Correct 3 ms 21636 KB Output is correct
14 Correct 177 ms 21636 KB Output is correct
15 Correct 66 ms 21636 KB Output is correct
16 Correct 1176 ms 21636 KB Output is correct
17 Correct 477 ms 21636 KB Output is correct
18 Correct 531 ms 21636 KB Output is correct
19 Correct 1602 ms 97888 KB Output is correct
20 Correct 1563 ms 105856 KB Output is correct
21 Correct 1783 ms 118664 KB Output is correct
22 Correct 1507 ms 126464 KB Output is correct
23 Correct 1518 ms 136880 KB Output is correct
24 Correct 1601 ms 146896 KB Output is correct
25 Correct 1703 ms 157276 KB Output is correct
26 Correct 1677 ms 169728 KB Output is correct
27 Correct 1631 ms 178800 KB Output is correct
28 Correct 1611 ms 186016 KB Output is correct
29 Correct 1737 ms 195060 KB Output is correct
30 Correct 1606 ms 205276 KB Output is correct