oj.uz

Submission #747371

# Submission time Handle Problem Language Result Execution time Memory
747371 2023-05-24T06:16:15 Z Zflop Wall (IOI14_wall) C++14
100 / 100
 1387 ms 215920 KB 
#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
/*
ID: 10002181
LANG: C++
TASK: lamps
*/
 
using str = string; // yay python!
using ld = long double; // or double, if TL is tight
using ll = long long;
using int64 = ll;
using db = double;
using ull = unsigned long long;
 
#define ch() getchar()
#define pc(x) putchar(x)
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
using vi = V<int>;
using vb = V<bool>;
using vpi = V<pair<int,int>>;
using vvi = V<vi>;
using vl = V<ll>;
using vd = V<ld>;
using vstr = V<str>;
 
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rev(x) reverse(all(x))
#define sz(x) (int)(x).size()
#define rall(x) x.rbegin(), x.rend()
#define AR array
 
// loops
#define F0R(i, a, b) for (int i=a; i<b;++i)
#define FOR(i, a) for (int i=0; i<a;++i)
#define FORn(i, a) for (int i=1; i<=a;++i)
#define ROF(i,a) for(int i=a-1; i >= 0;--i)
#define R0F(i,a,b) for(int i=a; i > b;--i)
#define ROFn(i,a) for(int i=a; i > 0;--i)
#define rep(a) FOR(_, a)
#define trav(i,x) for(auto& i:x)
 
// pairs
#define mp make_pair
#define pi pair <int, int>
#define f first
#define s second
 
// vectors
#define lb lower_bound
#define ub upper_bound
#define SUM(v) accumulate(all(v), 0LL)
#define MN(v) *min_element(all(v))
#define MX(v) *max_element(all(v))
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define eb emplace_back
#define ft front()
#define bk back()
#define ins insert
#define pf push_front
#define pb push_back
#define emt empty()
#define rsz resize
 
#define pob pop_back()
#define pof pop_front()
 
#define ts to_string
 
#define setIO()  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
 
ll MOD = 1e9+7;
const ll MAX = 100000000000;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
 
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
 
tcT> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; }
 
tcTU> T fstTrue(T lo, T hi, U f) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true
		T mid = lo+(hi-lo)/2;
		f(mid) ? hi = mid : lo = mid+1;
	}
	return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
	lo --; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find first index such that f is true
		T mid = lo+(hi-lo+1)/2;
		f(mid) ? lo = mid : hi = mid-1;
	}
	return lo;
}
 
//INPUT
#define tcTUU tcT, class ...U
tcT> void re(complex<T>& c);
tcTU> void re(pair<T,U>& p);
tcT> void re(V<T>& v);
tcT, size_t SZ> void re(AR<T,SZ>& a);
 
tcT> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
tcTUU> void re(T& t, U&... u) { re(t); re(u...); }
 
tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; }
tcTU> void re(pair<T,U>& p) { re(p.f,p.s); }
tcT> void re(V<T>& x) { trav(a,x) re(a); }
tcT> void rv(int n, V<T>& x) { x.rsz(n); re(x); }
 
//OUTPUT
namespace output {
	tcT> void PS(V<T>& x) { FOR(i,sz(x)) cout << x[i] << " \n"[i + 1 == sz(x)];}
	tcT> void W(pair<T,T>& x) { cout << x.f << ' ' << x.s << '\n'; }
	tcT> void PS(bool ok) { if(ok) cout << "YES\n"; else cout << "NO\n"; }
    template<class T1, class T2> void pr(const pair<T1,T2>& x);
    tcT, size_t SZ> void pr(const array<T,SZ>& x);
    tcT> void pr(const vector<T>& x);
    tcT> void pr(const set<T>& x);
    template<class T1, class T2> void pr(const map<T1,T2>& x);
 
    tcT> void pr(const T& x) { cout << x; }
    template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) {
        pr(first); pr(rest...);
    }
 
    template<class T1, class T2> void pr(const pair<T1,T2>& x) {
        pr("{",x.f,", ",x.s,"}");
    }
    tcT> void prContain(const T& x) {
        pr("{");
        bool fst = 1; trav(a,x) pr(!fst?", ":"",a), fst = 0;
        pr("}");
    }
    tcT, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); }
    tcT> void pr(const vector<T>& x) { prContain(x); }
    tcT> void pr(const set<T>& x) { prContain(x); }
    template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); }
 
    void ps() { pr("\n"); } // print w/ spaces
    template<class Arg> void ps(const Arg& first) { pr(first,"\n"); }
    template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) {
        pr(first," "); ps(rest...);
    }
}
 
using namespace output;
 
template<class T,class V> void add(T& a, const V& b) {
	a = (a + b) % MOD;
	}
template<class T,class V> void sub(T& a, const V& b) {
	a = (a - b + MOD) % MOD;
	}
template<class T,class V> void mult(T& a, const V& b) {
	a = a * b % MOD;
	}
 
void setF(string fileName = "") {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if((int)fileName.size()) {
		freopen((fileName+".in").c_str(), "r", stdin);
		freopen((fileName+".out").c_str(), "w", stdout);
	}
}
 
 
vb bb;
vi SIEVE(int N){ // sieve in O(N logN)
	vi pr;
	bb.rsz(N);
	bb[0] = bb[1] = true;
	vi g(N);
	F0R(i,2,N){
		if(!bb[i]){
			pr.pb(i);
			for (int j = i + i; j < N; j += i) bb[j] = true;
			}
		}
	return pr;
	}
 
 
 
template<class T> using ordset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
struct edge{
	int a;
	int b;
	int w;
	};
 
ll POW(ll x, ll y,ll mod){
    ll res = 1LL;
    x %= mod;
    while(y){
        if (y & 1LL)
            res *= x;
        res %= mod;
        x = (x*x) % mod;
        y >>= 1LL;
    }
    return res;
}
 
ll fact(ll x) { if(x) return x * fact(x - 1ll); return 1; }
 
vl fc;
void F(int N,ll MOD){
	fc.rsz(N + 1);
	fc[0] = 1;
	FORn(i,N) fc[i] = fc[i - 1] * i * 1ll % MOD;
	}
 
vl inv;
void I(int N,ll MOD){
	inv.rsz(N + 1);
	inv[N] = POW(fc[N],MOD - 2,MOD);
	for (int i = N; i ;--i) inv[i - 1] = inv[i] * 1ll * i % MOD;
	}
 
ll Cr(ll N,ll K,ll mod){
	if(K < 0) return 0;
	if(K > N) return 0;
	return fc[N] * 1ll * inv[K] % mod * inv[N - K] % mod;
	}
ll Ar(ll N,ll K,ll mod){
	return fc[N] * inv[N - K] % mod;
	}
ll iv(int k,ll MOD){
  return POW(k,MOD-2,MOD);
}
 
/*
 scanf("%lld", &testInteger);
 printf("%lld", testInteger);
 
 ____ ____ ____ ____ ____  ____
||f |||l |||o |||p |||p ||||y ||
||__|||__|||__|||__|||__||||__||
|/__\|/__\|/__\|/__\|/__\||/__\|
 
**/
const ll inf = (int)1e9;
int t;
bool ok;
template <class T> class SEG {
  private:
 
 
  public:
    int n;
	V<T>mi,ma;
	V<pair<T,T>> laz;
	vb ben;
	void init(int N){
		n = N;
		mi = ma = V<T>(6 * n);
		laz = V<pair<T,T>>(6 * n,{-inf,inf});
		ben = vb(6 * n);
		}

	
	void maxim(int node,int v){
		ckmax(mi[node],v);
		ckmax(ma[node],v);
		ckmax(laz[node].f,v);
		ckmax(laz[node].s,v);
		}
	
	void minim(int node,int v){
		ckmin(mi[node],v);
		ckmin(ma[node],v);
		ckmin(laz[node].f,v);
		ckmin(laz[node].s,v);
		}
	
	void lazy(int node){
		if(laz[node].f != -inf){
			maxim(2 * node,laz[node].f);
			maxim(2 * node + 1,laz[node].f);
			}
		if(laz[node].s != -inf){
			minim(2 * node,laz[node].s);
			minim(2 * node + 1,laz[node].s);
			}
		laz[node] = {-inf,inf};
		}
 
	
 
	void change(int a,int b,int v,int l,int r,int x){
	    if(a <= l && r <= b){
			ben[x] = true;
			if(ok){ // fst op, sets min
				maxim(x,v);
				}
			else{
				minim(x,v);
				}
            return;
        }
	    if(b < l || r < a) return;
	    lazy(x);
		int mid = (l + r) / 2;
		int f1 = 2 * x;
		int f2 = f1 | 1;
		change(a,b,v,l,mid,f1);
		change(a,b,v,mid + 1,r,f2);
		mi[x] = min(mi[2 * x],mi[2 * x + 1]);
		ma[x] = max(ma[2 * x],ma[2 * x + 1]);
		}
 
	void change(int l,int r,int v){
		change(l,r,v,1,n,1);
		}
 
    int get(int node,int l,int r,int x){
        if(l == r) return x;
        int mid = (l + r) / 2;
        lazy(x);
        if(node <= mid) return get(node,l,mid,2 * x);
        return get(node,mid + 1,r,2 * x + 1);
    }
 
    int get(int node){
        return get(node,1,n,1);
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SEG<int> C;
    C.init(n);
   // int xx = C.get(4);
    FOR(i,k){
        left[i]++;
        right[i]++;
        ++t;
        ok = true;
        if(op[i] == 1) C.change(left[i],right[i],height[i]);
        else {
			ok = false;
			C.change(left[i],right[i],height[i]);
			}
    }
    FOR(i,n){
        int& a = finalHeight[i];
		//ps(C.atleast[xx],C.atmost[xx],C.las1[xx],C.las2[xx]);
        int x = C.get(i + 1);
        a = C.mi[x];
        //ps(C.atleast[x],C.atmost[x],C.las1[x],C.las2[x]);
    }
    return;
}


// look out for out of bounds arrays
// And more importantly, is y a vowel? Damian:1
// <3 :L ._. <_<
// You have no idea how high I can fly
// code is my poetry

Compilation message

wall.cpp: In function 'void setF(std::string)':
wall.cpp:182:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |   freopen((fileName+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:183:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |   freopen((fileName+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 10 ms 1364 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 8 ms 1364 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 139 ms 13932 KB Output is correct
3 Correct 263 ms 9000 KB Output is correct
4 Correct 747 ms 27604 KB Output is correct
5 Correct 403 ms 28252 KB Output is correct
6 Correct 385 ms 26640 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 10 ms 1364 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 7 ms 1392 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 150 ms 13940 KB Output is correct
9 Correct 254 ms 9124 KB Output is correct
10 Correct 715 ms 27604 KB Output is correct
11 Correct 414 ms 28160 KB Output is correct
12 Correct 382 ms 26680 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 145 ms 13932 KB Output is correct
15 Correct 49 ms 3004 KB Output is correct
16 Correct 899 ms 27612 KB Output is correct
17 Correct 432 ms 27028 KB Output is correct
18 Correct 440 ms 27032 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 360 KB Output is correct
4 Correct 10 ms 1464 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 7 ms 1364 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 155 ms 13944 KB Output is correct
9 Correct 273 ms 9036 KB Output is correct
10 Correct 762 ms 27580 KB Output is correct
11 Correct 409 ms 28164 KB Output is correct
12 Correct 391 ms 26572 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 147 ms 13872 KB Output is correct
15 Correct 50 ms 3004 KB Output is correct
16 Correct 870 ms 27700 KB Output is correct
17 Correct 401 ms 27060 KB Output is correct
18 Correct 389 ms 26912 KB Output is correct
19 Correct 1387 ms 215836 KB Output is correct
20 Correct 1333 ms 215732 KB Output is correct
21 Correct 1342 ms 215736 KB Output is correct
22 Correct 1344 ms 215740 KB Output is correct
23 Correct 1342 ms 215840 KB Output is correct
24 Correct 1357 ms 215760 KB Output is correct
25 Correct 1341 ms 215692 KB Output is correct
26 Correct 1348 ms 215800 KB Output is correct
27 Correct 1342 ms 215920 KB Output is correct
28 Correct 1316 ms 215776 KB Output is correct
29 Correct 1350 ms 215884 KB Output is correct
30 Correct 1364 ms 215780 KB Output is correct