oj.uz

Submission #52259

# Submission time Handle Problem Language Result Execution time Memory
52259 2018-06-25T07:02:27 Z rondojim Wall (IOI14_wall) C++17
32 / 100
 921 ms 153872 KB 
#include "wall.h"
 
#include <bits/stdc++.h>
 
#define pb push_back
#define fr first
#define sc second
#define mk make_pair
 
using namespace std;
 
const int N = (int) 2e5 + 6;
 
int nn;
vector <pair<int,pair<int,int> > > add,cut;
vector <int> mx,mn;
 
struct node {
      int c,a;
      node () {
            c = 0,a = -1;
      }
}t[N * 4],tt[N * 4];
 
void push (int v,int tl,int tr) {
      if (t[v].a != -1 && tl < tr) {
            if (t[v + v].a == -1) t[v + v].a = t[v].a;
            if (t[v + v + 1].a == -1) t[v + v + 1].a = t[v].a;
            t[v].a = -1;
      }
}
void update (int l,int r,int h,int v = 1,int tl = 0,int tr = nn - 1) {
      push(v,tl,tr);
      if (tl > r || tr < l || t[v].a != -1)
            return;
      if (l <= tl && tr <= r) {
            t[v].a = h;
            push(v,tl,tr);
      }
      else {
            int tm = (tl + tr) >> 1;
            update (l,r,h,v + v,tl,tm);
            update (l,r,h,v + v + 1,tm + 1,tr);
 
            push(v,tl,tr);
            push(v + v,tl,tm);
            push(v + v + 1,tm + 1,tr);
      }
}
void push1(int v,int tl,int tr) {
      if (tt[v].a != -1 && tl < tr) {
            if (tt[v + v].a == -1) tt[v + v].a = tt[v].a;
            if (tt[v + v + 1].a == -1) tt[v + v + 1].a = tt[v].a;
            tt[v].a = -1;
      }
}
void update1 (int l,int r,int h,int v = 1,int tl = 0,int tr = nn - 1) {
      push1(v,tl,tr);
      if (tl > r || tr < l || tt[v].a != -1)
            return;
      if (l <= tl && tr <= r) {
            tt[v].a = h;
            push1(v,tl,tr);
      }
      else {
            int tm = (tl + tr) >> 1;
            update1 (l,r,h,v + v,tl,tm);
            update1 (l,r,h,v + v + 1,tm + 1,tr);
 
            push1(v,tl,tr);
            push1(v + v,tl,tm);
            push1(v + v + 1,tm + 1,tr);
      }
}
void init (int v = 1,int tl = 0,int tr = nn - 1) {
            push(v,tl,tr);
      if (tl == tr) {
            mx.pb(t[v].a);
      }
      else {
            int tm = (tl + tr) >> 1;
            init(v + v,tl,tm);
            init(v + v + 1,tm + 1,tr);
      }
}
void init1 (int v = 1,int tl = 0,int tr = nn - 1) {
      push1(v,tl,tr);
      if (tl == tr) {
            mn.pb(tt[v].a);
      }
      else {
            int tm = (tl + tr) >> 1;
            init1(v + v,tl,tm);
            init1(v + v + 1,tm + 1,tr);
      }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
      nn = n;
      if (n <= 10000 && k <= 5000) {
            for (int i = 0; i < k; i ++) {
                  int type = op[i];
                  int l = left[i];
                  int r = right[i];
                  int h = height[i];
 
                  if (type == 1) {
                        for (int j = l; j <= r; j ++)
                              finalHeight[j] = max(finalHeight[j],h);
                  }
                  else {
                        for (int j = l; j <= r; j ++)
                              finalHeight[j] = min(finalHeight[j],h);
                  }
            }
      }
      else {
            for (int i = 0; i < k; i ++) {
                  int type = op[i];
                  int l = left[i];
                  int r = right[i];
                  int h = height[i];
                  if (type == 1) add.pb({h,{l,r}});
                  else cut.pb({h,{l,r}});
            }
            sort (add.rbegin(),add.rend());
            sort (cut.begin(),cut.end());
 
            for (auto to : add)
                  update (to.sc.fr,to.sc.sc,to.fr);
            for (auto to : cut)
                  update1 (to.sc.fr,to.sc.sc,to.fr);
 
            init();
            init1();
 
            for (int i = 0; i < nn; i ++) {
                  finalHeight[i] = 0;
                  if (mx[i] != -1) finalHeight[i] = mx[i];
                  if (mn[i] != -1) finalHeight[i] = min(mn[i],finalHeight[i]);
            }
      }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12796 KB Output is correct
2 Correct 13 ms 13168 KB Output is correct
3 Correct 13 ms 13176 KB Output is correct
4 Correct 29 ms 13432 KB Output is correct
5 Correct 40 ms 13572 KB Output is correct
6 Correct 28 ms 13704 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 13704 KB Output is correct
2 Correct 252 ms 34672 KB Output is correct
3 Correct 297 ms 34672 KB Output is correct
4 Correct 870 ms 48420 KB Output is correct
5 Correct 407 ms 59200 KB Output is correct
6 Correct 379 ms 67712 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 67712 KB Output is correct
2 Correct 14 ms 67712 KB Output is correct
3 Correct 13 ms 67712 KB Output is correct
4 Correct 28 ms 67712 KB Output is correct
5 Correct 30 ms 67712 KB Output is correct
6 Correct 28 ms 67712 KB Output is correct
7 Correct 12 ms 67712 KB Output is correct
8 Correct 243 ms 73000 KB Output is correct
9 Correct 296 ms 73000 KB Output is correct
10 Correct 845 ms 86932 KB Output is correct
11 Correct 421 ms 97852 KB Output is correct
12 Correct 401 ms 106144 KB Output is correct
13 Correct 13 ms 106144 KB Output is correct
14 Incorrect 270 ms 109724 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 109724 KB Output is correct
2 Correct 14 ms 109724 KB Output is correct
3 Correct 13 ms 109724 KB Output is correct
4 Correct 28 ms 109724 KB Output is correct
5 Correct 34 ms 109724 KB Output is correct
6 Correct 34 ms 109724 KB Output is correct
7 Correct 12 ms 109724 KB Output is correct
8 Correct 375 ms 117376 KB Output is correct
9 Correct 315 ms 117376 KB Output is correct
10 Correct 921 ms 131144 KB Output is correct
11 Correct 420 ms 141932 KB Output is correct
12 Correct 417 ms 150388 KB Output is correct
13 Correct 12 ms 150388 KB Output is correct
14 Incorrect 253 ms 153872 KB Output isn't correct
15 Halted 0 ms 0 KB -