oj.uz

Submission #895959

# Submission time Handle Problem Language Result Execution time Memory
895959 2023-12-31T08:27:09 Z SalihSahin Wall (IOI14_wall) C++14
8 / 100
 3000 ms 19108 KB 
#include<bits/stdc++.h>
#include "wall.h"
#define pb push_back
#define mp make_pair
using namespace std;

const int mod = 1e9 + 7;
const int N = 3e5 + 5;

struct SEGT{
    vector<int> mx, mn, lazy;

    void init(int n){
        lazy.assign(4*n, -1);
        mx.assign(4*n, 0);
        mn.assign(4*n, 0);
    }

    void push(int ind){
        if(lazy[ind] == -1) return;
        mx[ind*2] = lazy[ind];
        mx[ind*2+1] = lazy[ind];
        mn[ind*2] = lazy[ind];
        mn[ind*2+1] = lazy[ind];
        lazy[ind*2] = lazy[ind];
        lazy[ind*2+1] = lazy[ind];

        lazy[ind] = -1;
    }

    void update1(int ind, int l, int r, int ql, int qr, int val){
        if(l > r || l > qr || r < ql) return;
        if(l >= ql && r <= qr && mx[ind] < val){
            lazy[ind] = val;
            mx[ind] = val;
            mn[ind] = val;
        }
        else if(l >= ql && r <= qr && mn[ind] > val) return;
        else if(l == r){
            mx[ind] = max(mx[ind], val);
            mn[ind] = mx[ind];
        }
        else{
            push(ind);
            int m = (l + r)/2;

            update1(ind*2, l, m, ql, qr, val);
            update1(ind*2+1, m+1, r, ql, qr, val);

            mx[ind] = max(mx[ind*2], mx[ind*2+1]);
            mn[ind] = min(mn[ind*2], mn[ind*2+1]);
        }
    }

    void update2(int ind, int l, int r, int ql, int qr, int val){
        if(l > r || l > qr || r < ql) return;
        if(l >= ql && r <= qr && mn[ind] > val){
            lazy[ind] = val;
            mx[ind] = val;
            mn[ind] = val;
        }
        else if(l >= ql && r <= qr && mx[ind] < val) return;
        else if(l == r){
            mx[ind] = max(mx[ind], val);
            mn[ind] = mx[ind];
        }
        else{
            push(ind);
            int m = (l + r)/2;

            update2(ind*2, l, m, ql, qr, val);
            update2(ind*2+1, m+1, r, ql, qr, val);

            mx[ind] = max(mx[ind*2], mx[ind*2+1]);
            mn[ind] = min(mn[ind*2], mn[ind*2+1]);
        }
    }

    void query(int ind, int l, int r, vector<int> &a){
        if(l == r) a[l] = mx[ind];
        else{
            push(ind);
            int m = (l + r)/2;

            query(ind*2, l, m, a);
            query(ind*2+1, m+1, r, a);
        }
    }

};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
   SEGT seg;
   seg.init(n);
   for(int i = 0; i < k; i++){
     if(op[i] == 1) seg.update1(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
     else seg.update2(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
   }
   vector<int> a(n+1);
   seg.query(1, 1, n, a);

   for(int i = 0; i < n; i++){
     finalHeight[i] = a[i+1];
   }
}

/*
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;
}
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1112 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 5 ms 1128 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 117 ms 11228 KB Output is correct
3 Correct 121 ms 6580 KB Output is correct
4 Correct 352 ms 18848 KB Output is correct
5 Execution timed out 3053 ms 18328 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 113 ms 11288 KB Output is correct
9 Correct 122 ms 6648 KB Output is correct
10 Correct 355 ms 19108 KB Output is correct
11 Execution timed out 3050 ms 18308 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 496 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 5 ms 1132 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 0 ms 388 KB Output is correct
8 Correct 117 ms 11248 KB Output is correct
9 Correct 122 ms 6736 KB Output is correct
10 Correct 379 ms 18652 KB Output is correct
11 Execution timed out 3062 ms 18092 KB Time limit exceeded
12 Halted 0 ms 0 KB -