oj.uz

Submission #50180

# Submission time Handle Problem Language Result Execution time Memory
50180 2018-06-08T07:06:20 Z Talant Wall (IOI14_wall) C++17
32 / 100
 946 ms 29472 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 12792 KB Output is correct
2 Correct 14 ms 13040 KB Output is correct
3 Correct 13 ms 13040 KB Output is correct
4 Correct 28 ms 13168 KB Output is correct
5 Correct 29 ms 13192 KB Output is correct
6 Correct 28 ms 13216 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 13216 KB Output is correct
2 Correct 250 ms 28356 KB Output is correct
3 Correct 289 ms 28356 KB Output is correct
4 Correct 894 ms 28752 KB Output is correct
5 Correct 492 ms 29368 KB Output is correct
6 Correct 410 ms 29368 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29368 KB Output is correct
2 Correct 13 ms 29368 KB Output is correct
3 Correct 13 ms 29368 KB Output is correct
4 Correct 28 ms 29368 KB Output is correct
5 Correct 42 ms 29368 KB Output is correct
6 Correct 41 ms 29368 KB Output is correct
7 Correct 12 ms 29368 KB Output is correct
8 Correct 263 ms 29368 KB Output is correct
9 Correct 308 ms 29368 KB Output is correct
10 Correct 946 ms 29368 KB Output is correct
11 Correct 592 ms 29408 KB Output is correct
12 Correct 471 ms 29408 KB Output is correct
13 Correct 11 ms 29408 KB Output is correct
14 Incorrect 241 ms 29408 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29408 KB Output is correct
2 Correct 14 ms 29408 KB Output is correct
3 Correct 14 ms 29408 KB Output is correct
4 Correct 32 ms 29408 KB Output is correct
5 Correct 29 ms 29408 KB Output is correct
6 Correct 29 ms 29408 KB Output is correct
7 Correct 11 ms 29408 KB Output is correct
8 Correct 262 ms 29408 KB Output is correct
9 Correct 314 ms 29408 KB Output is correct
10 Correct 855 ms 29408 KB Output is correct
11 Correct 378 ms 29472 KB Output is correct
12 Correct 435 ms 29472 KB Output is correct
13 Correct 14 ms 29472 KB Output is correct
14 Incorrect 276 ms 29472 KB Output isn't correct
15 Halted 0 ms 0 KB -