oj.uz

Submission #422888

# Submission time Handle Problem Language Result Execution time Memory
422888 2021-06-10T13:42:15 Z fedoseevtimofey Wall (IOI14_wall) C++14
100 / 100
 766 ms 152164 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
#include <chrono>
 
using namespace std;
 
typedef long long ll;

#include "wall.h"

const int Inf = 1e9;

struct Chel {
  int l, r;
  Chel() : l(0), r(Inf) {}
  Chel(int l, int r) : l(l), r(r) {}
  Chel operator +(const Chel &other) const {
    if (r < other.l) return Chel(other.l, other.l);
    if (l > other.r) return Chel(other.r, other.r);
    return Chel(max(l, other.l), min(r, other.r));
  }
};

const int N = 1 << 19;

Chel t[1 << 20];
int sz;

void modify(int pos, Chel val) {
  t[N + pos] = val;
  //cout << "add " << pos << ' ' << val.l << ' ' << val.r << endl;
  for (int i = (N + pos) / 2; i >= 1; i /= 2) {
    t[i] = t[2 * i] + t[2 * i + 1];
  }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  //cout << k << endl;
  vector <vector <int>> beg(n), en(n);
  for (int i = 0; i < k; ++i) {
    beg[left[i]].push_back(i);
    en[right[i]].push_back(i);
  }
  for (int i = 0; i < n; ++i) {
    for (int id : beg[i]) {
      if (op[id] == 1) {
        modify(id, Chel(height[id], Inf));
      } else {
        modify(id, Chel(0, height[id]));
      }
    }
    //cout << "go " << i << ' ' << t[1].l << ' ' << t[1].r << endl;
    finalHeight[i] = t[1].l;
    for (int id : en[i]) {
      modify(id, Chel());
    }
  }
}

#ifdef LOCAL
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n;
  int k;

  int i, j;  
  int status = 0;

  cin >> n >> k;

  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++){
    cin >> op[i] >> left[i] >> right[i] >> height[i];
  }

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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8396 KB Output is correct
2 Correct 10 ms 8652 KB Output is correct
3 Correct 7 ms 8524 KB Output is correct
4 Correct 12 ms 9404 KB Output is correct
5 Correct 11 ms 9292 KB Output is correct
6 Correct 11 ms 9292 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8448 KB Output is correct
2 Correct 309 ms 26176 KB Output is correct
3 Correct 184 ms 19696 KB Output is correct
4 Correct 697 ms 40488 KB Output is correct
5 Correct 317 ms 38820 KB Output is correct
6 Correct 286 ms 36868 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8396 KB Output is correct
2 Correct 8 ms 8636 KB Output is correct
3 Correct 8 ms 8556 KB Output is correct
4 Correct 11 ms 9340 KB Output is correct
5 Correct 10 ms 9292 KB Output is correct
6 Correct 10 ms 9344 KB Output is correct
7 Correct 5 ms 8396 KB Output is correct
8 Correct 257 ms 26280 KB Output is correct
9 Correct 217 ms 19724 KB Output is correct
10 Correct 633 ms 40348 KB Output is correct
11 Correct 328 ms 38848 KB Output is correct
12 Correct 300 ms 36940 KB Output is correct
13 Correct 5 ms 8496 KB Output is correct
14 Correct 277 ms 26280 KB Output is correct
15 Correct 35 ms 11184 KB Output is correct
16 Correct 766 ms 40340 KB Output is correct
17 Correct 333 ms 37324 KB Output is correct
18 Correct 327 ms 37104 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8396 KB Output is correct
2 Correct 11 ms 8700 KB Output is correct
3 Correct 8 ms 8524 KB Output is correct
4 Correct 12 ms 9420 KB Output is correct
5 Correct 11 ms 9280 KB Output is correct
6 Correct 11 ms 9292 KB Output is correct
7 Correct 6 ms 8396 KB Output is correct
8 Correct 270 ms 26344 KB Output is correct
9 Correct 174 ms 19756 KB Output is correct
10 Correct 635 ms 40408 KB Output is correct
11 Correct 295 ms 38836 KB Output is correct
12 Correct 305 ms 36884 KB Output is correct
13 Correct 6 ms 8396 KB Output is correct
14 Correct 305 ms 26276 KB Output is correct
15 Correct 46 ms 11204 KB Output is correct
16 Correct 688 ms 40508 KB Output is correct
17 Correct 336 ms 37424 KB Output is correct
18 Correct 387 ms 37056 KB Output is correct
19 Correct 653 ms 151996 KB Output is correct
20 Correct 650 ms 152028 KB Output is correct
21 Correct 674 ms 152032 KB Output is correct
22 Correct 645 ms 152060 KB Output is correct
23 Correct 632 ms 152104 KB Output is correct
24 Correct 631 ms 152088 KB Output is correct
25 Correct 696 ms 151996 KB Output is correct
26 Correct 661 ms 152052 KB Output is correct
27 Correct 670 ms 151980 KB Output is correct
28 Correct 640 ms 151984 KB Output is correct
29 Correct 664 ms 151984 KB Output is correct
30 Correct 642 ms 152164 KB Output is correct