oj.uz

Submission #312743

# Submission time Handle Problem Language Result Execution time Memory
312743 2020-10-14T09:22:58 Z aloo123 Wall (IOI14_wall) C++14
100 / 100
 1804 ms 262144 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double; 
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>; 
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>; 
using vpd = vector<pd>;

#define tcT template<class T
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 

// pairs
#define mp make_pair
#define f first
#define s second

// vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const ll N = 4e7;

class SegmentTree {
  const ll inf = 1e18;
  int n, n0;
  ll max_v[4*N], smax_v[4*N], max_c[4*N];
  ll min_v[4*N], smin_v[4*N], min_c[4*N];
  ll sum[4*N];

  void update_node_max(int k, ll x) {
    sum[k] += (x - max_v[k]) * max_c[k];

    if(max_v[k] == min_v[k]) {
      max_v[k] = min_v[k] = x;
    } else if(max_v[k] == smin_v[k]) {
      max_v[k] = smin_v[k] = x;
    } else {
      max_v[k] = x;
    }
  }
  void update_node_min(int k, ll x) {
    sum[k] += (x - min_v[k]) * min_c[k];

    if(max_v[k] == min_v[k]) {
      max_v[k] = min_v[k] = x;
    } else if(smax_v[k] == min_v[k]) {
      min_v[k] = smax_v[k] = x;
    } else {
      min_v[k] = x;
    }
  }

  void push(int k) {
    if(max_v[k] < max_v[2*k+1]) {
      update_node_max(2*k+1, max_v[k]);
    }
    if(min_v[2*k+1] < min_v[k]) {
      update_node_min(2*k+1, min_v[k]);
    }

    if(max_v[k] < max_v[2*k+2]) {
      update_node_max(2*k+2, max_v[k]);
    }
    if(min_v[2*k+2] < min_v[k]) {
      update_node_min(2*k+2, min_v[k]);
    }
  }

  void update(int k) {
    sum[k] = sum[2*k+1] + sum[2*k+2];

    if(max_v[2*k+1] < max_v[2*k+2]) {
      max_v[k] = max_v[2*k+2];
      max_c[k] = max_c[2*k+2];
      smax_v[k] = max(max_v[2*k+1], smax_v[2*k+2]);
    } else if(max_v[2*k+1] > max_v[2*k+2]) {
      max_v[k] = max_v[2*k+1];
      max_c[k] = max_c[2*k+1];
      smax_v[k] = max(smax_v[2*k+1], max_v[2*k+2]);
    } else {
      max_v[k] = max_v[2*k+1];
      max_c[k] = max_c[2*k+1] + max_c[2*k+2];
      smax_v[k] = max(smax_v[2*k+1], smax_v[2*k+2]);
    }

    if(min_v[2*k+1] < min_v[2*k+2]) {
      min_v[k] = min_v[2*k+1];
      min_c[k] = min_c[2*k+1];
      smin_v[k] = min(smin_v[2*k+1], min_v[2*k+2]);
    } else if(min_v[2*k+1] > min_v[2*k+2]) {
      min_v[k] = min_v[2*k+2];
      min_c[k] = min_c[2*k+2];
      smin_v[k] = min(min_v[2*k+1], smin_v[2*k+2]);
    } else {
      min_v[k] = min_v[2*k+1];
      min_c[k] = min_c[2*k+1] + min_c[2*k+2];
      smin_v[k] = min(smin_v[2*k+1], smin_v[2*k+2]);
    }
  }

  void _update_min(ll x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a || max_v[k] <= x) {
      return;
    }
    if(a <= l && r <= b && smax_v[k] < x) {
      update_node_max(k, x);
      return;
    }

    push(k);
    _update_min(x, a, b, 2*k+1, l, (l+r)/2);
    _update_min(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }

  void _update_max(ll x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a || x <= min_v[k]) {
      return;
    }
    if(a <= l && r <= b && x < smin_v[k]) {
      update_node_min(k, x);
      return;
    }

    push(k);
    _update_max(x, a, b, 2*k+1, l, (l+r)/2);
    _update_max(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }

  ll _query_max(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return -inf;
    }
    if(a <= l && r <= b) {
      return max_v[k];
    }
    push(k);
    ll lv = _query_max(a, b, 2*k+1, l, (l+r)/2);
    ll rv = _query_max(a, b, 2*k+2, (l+r)/2, r);
    return max(lv, rv);
  }

  ll _query_min(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return inf;
    }
    if(a <= l && r <= b) {
      return min_v[k];
    }
    push(k);
    ll lv = _query_min(a, b, 2*k+1, l, (l+r)/2);
    ll rv = _query_min(a, b, 2*k+2, (l+r)/2, r);
    return min(lv, rv);
  }

  ll _query_sum(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return 0;
    }
    if(a <= l && r <= b) {
      return sum[k];
    }
    push(k);
    ll lv = _query_sum(a, b, 2*k+1, l, (l+r)/2);
    ll rv = _query_sum(a, b, 2*k+2, (l+r)/2, r);
    return lv + rv;
  }

public:
  SegmentTree(int n) {
    SegmentTree(n, nullptr);
  }

  SegmentTree(int n, ll *a) : n(n) {
    n0 = 1;
    while(n0 < n) n0 <<= 1;

    for(int i=0; i<n; ++i) {
      max_v[n0-1+i] = min_v[n0-1+i] = sum[n0-1+i] = (a != nullptr ? a[i] : 0);
      smax_v[n0-1+i] = -inf;
      smin_v[n0-1+i] = inf;
      max_c[n0-1+i] = min_c[n0-1+i] = 1;
    }
    for(int i=n; i<n0; ++i) {
      max_v[n0-1+i] = smax_v[n0-1+i] = -inf;
      min_v[n0-1+i] = smin_v[n0-1+i] = inf;
      max_c[n0-1+i] = min_c[n0-1+i] = 0;
    }
    for(int i=n0-2; i>=0; i--) update(i);
  }

  void update_min(int a, int b, ll x) {
    return _update_min(x, a, b, 0, 0, n0);
  }

  void update_max(int a, int b, ll x) {
    return _update_max(x, a, b, 0, 0, n0);
  }

  ll query_max(int a, int b) {
    return _query_max(a, b, 0, 0, n0);
  }

  ll query_min(int a, int b) {
    return _query_min(a, b, 0, 0, n0);
  }

  ll query_sum(int a, int b) {
    return _query_sum(a, b, 0, 0, n0);
  }
};




void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]){
	ll v[n];
	for(int i = 0;i<n;i++) v[i] = 0;
	SegmentTree stb(n,v);
	for(int i = 0;i<k;i++){
		int l = left[i];
		int r = right[i];
		int h = height[i];
		r++;
		if(op[i] == 1){
			stb.update_max(l,r,h);
		}
		else stb.update_min(l,r,h);
	}
	for(int i = 0;i<n;i++){
		finalHeight[i] = stb.query_max(i,i+1);
		// cout<<finalHeight[i] << " "; 
	}

	// cout << endl;
	
}

// int main() {
// 	setIO();	
// 	int n;
// 	cin>>n;
// 	int q;
// 	cin>>q;
// 	int op[q],left[q],right[q],height[q],finalHeight[n];
// 	for(int i = 0;i<q;i++){
// 		cin >> op[i];
// 		cin >> left[i] >> right[i] >> height[i];
// 	}
// 	for(int i = 0;i<n;i++) finalHeight[i] = 0;
// 	buildWall(n,q,op,left,right,height,finalHeight);
// 	// you should actually read the stuff at the bottom

// }

/* stuff you should look for
	* read the probem 3 more times in case of WA :)
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 12 ms 2432 KB Output is correct
5 Correct 10 ms 2432 KB Output is correct
6 Correct 10 ms 2432 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 172 ms 8184 KB Output is correct
3 Correct 107 ms 7416 KB Output is correct
4 Correct 267 ms 23776 KB Output is correct
5 Correct 273 ms 24312 KB Output is correct
6 Correct 339 ms 24312 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 12 ms 2432 KB Output is correct
5 Correct 10 ms 2432 KB Output is correct
6 Correct 10 ms 2432 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 169 ms 8184 KB Output is correct
9 Correct 106 ms 7396 KB Output is correct
10 Correct 266 ms 23800 KB Output is correct
11 Correct 265 ms 24312 KB Output is correct
12 Correct 348 ms 24440 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 174 ms 8332 KB Output is correct
15 Correct 60 ms 4728 KB Output is correct
16 Correct 1234 ms 24056 KB Output is correct
17 Correct 545 ms 24056 KB Output is correct
18 Correct 535 ms 24056 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 12 ms 2432 KB Output is correct
5 Correct 10 ms 2432 KB Output is correct
6 Correct 11 ms 2396 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 166 ms 8184 KB Output is correct
9 Correct 106 ms 7420 KB Output is correct
10 Correct 263 ms 23704 KB Output is correct
11 Correct 269 ms 24312 KB Output is correct
12 Correct 336 ms 24184 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 178 ms 8220 KB Output is correct
15 Correct 61 ms 4600 KB Output is correct
16 Correct 1228 ms 24148 KB Output is correct
17 Correct 534 ms 24056 KB Output is correct
18 Correct 537 ms 24072 KB Output is correct
19 Correct 1772 ms 262144 KB Output is correct
20 Correct 1760 ms 262144 KB Output is correct
21 Correct 1782 ms 262144 KB Output is correct
22 Correct 1757 ms 262144 KB Output is correct
23 Correct 1770 ms 262144 KB Output is correct
24 Correct 1804 ms 262144 KB Output is correct
25 Correct 1753 ms 262144 KB Output is correct
26 Correct 1767 ms 262144 KB Output is correct
27 Correct 1779 ms 262144 KB Output is correct
28 Correct 1771 ms 262144 KB Output is correct
29 Correct 1771 ms 262144 KB Output is correct
30 Correct 1773 ms 262144 KB Output is correct