oj.uz

Submission #216725

# Submission time Handle Problem Language Result Execution time Memory
216725 2020-03-27T22:45:28 Z rqi Wall (IOI14_wall) C++14
100 / 100
 1171 ms 164076 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair 
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#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 

#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 int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 

template<class T> bool ckmin(T& a, const T& b) { 
    return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
    return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> 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); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
template<class A, class B> str ts(pair<A,B> p);
template<class A> str ts(complex<A> c) { return ts(mp(c.real(),c.imag())); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(char c) { str s = ""; s += c; return s; }
str ts(str s) { return s; }
str ts(const char* s) { return (str)s; }
str ts(vector<bool> v) { 
    bool fst = 1; str res = "{";
    F0R(i,sz(v)) {
        if (!fst) res += ", ";
        fst = 0; res += ts(v[i]);
    }
    res += "}"; return res;
}
template<size_t SZ> str ts(bitset<SZ> b) {
    str res = ""; F0R(i,SZ) res += char('0'+b[i]);
    return res; }
template<class T> str ts(T v) {
    bool fst = 1; str res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += ts(x);
    }
    res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
    return "("+ts(p.f)+", "+ts(p.s)+")"; }

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
    pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
    pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
    unsyncIO();
    // cin.exceptions(cin.failbit); 
    // throws exception when do smth illegal
    // ex. try to read letter into int
    if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

/**
 * Description: 1D range update and query. Set SZ to a power of 2.
 * Source: USACO Counting Haybales
 * Verification: SPOJ Horrible
 */

template<class T, int SZ> struct LazySeg { 
    T mx[2*SZ], mn[2*SZ]; 
    LazySeg() { F0R(i,2*SZ){ mx[i] = 0; mn[i] = MOD; }}
    void pull(int ind) { mx[ind] = max(mx[2*ind], mx[2*ind+1]); mn[ind] = min(mn[2*ind], mn[2*ind+1]);}
    void build() { ROF(i,1,SZ) pull(i); }
    void updmn(int pos, T val, int ind=1,int L=0, int R=SZ-1) {
        if (pos < L || R < pos) return;
        if (L == R && pos == L) { 
            mn[ind] = val; return; }
        int M = (L+R)/2;
        updmn(pos, val, 2*ind,L,M); updmn(pos, val,2*ind+1,M+1,R); 
        pull(ind);
    }
    void updmx(int pos, T val, int ind=1,int L=0, int R=SZ-1) {
        if (pos < L || R < pos) return;
        if (L == R && pos == L) { 
            mx[ind] = val; return; }
        int M = (L+R)/2;
        updmx(pos, val, 2*ind,L,M); updmx(pos, val,2*ind+1,M+1,R); 
        pull(ind);
    }
    
    pair<int, pi> qjump(int curmn = MOD, int curmx = 0, int ind = 1, int L = 0, int R = SZ-1){
        //return leftmost point in interval that works
        if(max(curmx, mx[ind]) <= min(curmn, mn[ind])) return mp(L, mp(min(curmn, mn[ind]), max(curmx, mx[ind])));
        if(L == R) return mp(MOD, mp(min(curmn, mn[ind]), max(curmx, mx[ind])));
        int M = (L+R)/2;
        pair<int, pi> rans = qjump(curmn, curmx, 2*ind+1, M+1, R);
        if(rans.f == M+1){
            pair<int, pi> oans = qjump(min(curmn, mn[2*ind+1]), max(curmx, mx[2*ind+1]), 2*ind, L, M);
            if(oans.f == MOD){
                return rans;
            }
            return oans;
        }
        else{
            return rans;
        }
    }
};



LazySeg<int,524288> lseg;

vector<pair<pi, int>> st[2000005]; //time, operation type, height
vector<pair<pi, int>> en[2000005];

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	lseg.build();
	for(int i = 1; i <= k; i++){
		st[left[i-1]].pb(mp(mp(i, op[i-1]), height[i-1]));
		en[right[i-1]+1].pb(mp(mp(i, op[i-1]), height[i-1]));
	}

	for(int i = 0; i < n; i++){
		if((i != 0) && (sz(st[i]) == 0) && (sz(en[i]) == 0)){
			finalHeight[i] = finalHeight[i-1];
		}
		//process st
		for(auto u: st[i]){
			if(u.f.s == 1){
				//adding
				lseg.updmx(u.f.f, u.s);
			}
			else{
				//removing
				lseg.updmn(u.f.f, u.s);
			}
		}
		//process en
		for(auto u: en[i]){
			if(u.f.s == 1){
				//adding
				lseg.updmx(u.f.f, 0);
			}
			else{
				//removing
				lseg.updmn(u.f.f, MOD);
			}
		}
		//process query
		pair<int, pi> res = lseg.qjump();
		dbg(i, res);
		int ind = res.f-1;
		int lo = res.s.s;
		int hi = res.s.f;
		dbg(i, lo, hi);
		if(ind <= 0){
			finalHeight[i] = lo;
		}
		else if(lseg.mx[ind+524288] == 0){
			finalHeight[i] = lo;
		}
		else{
			finalHeight[i] = hi;
		}
	}

	return;
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:226:14: warning: statement has no effect [-Wunused-value]
   dbg(i, res);
              ^
wall.cpp:230:17: warning: statement has no effect [-Wunused-value]
   dbg(i, lo, hi);
                 ^
wall.cpp: In function 'void setIn(std::__cxx11::string)':
wall.cpp:124:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
wall.cpp: In function 'void setOut(std::__cxx11::string)':
wall.cpp:125:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 102392 KB Output is correct
2 Correct 65 ms 102904 KB Output is correct
3 Correct 64 ms 102648 KB Output is correct
4 Correct 70 ms 103032 KB Output is correct
5 Correct 70 ms 102904 KB Output is correct
6 Correct 69 ms 102904 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 102392 KB Output is correct
2 Correct 341 ms 128188 KB Output is correct
3 Correct 290 ms 118008 KB Output is correct
4 Correct 811 ms 140672 KB Output is correct
5 Correct 495 ms 139552 KB Output is correct
6 Correct 471 ms 137208 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 102392 KB Output is correct
2 Correct 65 ms 102776 KB Output is correct
3 Correct 63 ms 102648 KB Output is correct
4 Correct 70 ms 103032 KB Output is correct
5 Correct 74 ms 103032 KB Output is correct
6 Correct 69 ms 103032 KB Output is correct
7 Correct 61 ms 102392 KB Output is correct
8 Correct 339 ms 128148 KB Output is correct
9 Correct 303 ms 118120 KB Output is correct
10 Correct 837 ms 140784 KB Output is correct
11 Correct 482 ms 139512 KB Output is correct
12 Correct 470 ms 137068 KB Output is correct
13 Correct 64 ms 102392 KB Output is correct
14 Correct 338 ms 128148 KB Output is correct
15 Correct 101 ms 104952 KB Output is correct
16 Correct 852 ms 141024 KB Output is correct
17 Correct 522 ms 137452 KB Output is correct
18 Correct 519 ms 136696 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 102392 KB Output is correct
2 Correct 66 ms 102776 KB Output is correct
3 Correct 66 ms 102648 KB Output is correct
4 Correct 73 ms 103032 KB Output is correct
5 Correct 71 ms 102904 KB Output is correct
6 Correct 72 ms 102904 KB Output is correct
7 Correct 68 ms 102648 KB Output is correct
8 Correct 350 ms 128280 KB Output is correct
9 Correct 290 ms 118008 KB Output is correct
10 Correct 833 ms 140660 KB Output is correct
11 Correct 487 ms 139512 KB Output is correct
12 Correct 480 ms 137180 KB Output is correct
13 Correct 65 ms 102392 KB Output is correct
14 Correct 347 ms 128148 KB Output is correct
15 Correct 109 ms 104952 KB Output is correct
16 Correct 836 ms 140920 KB Output is correct
17 Correct 521 ms 137336 KB Output is correct
18 Correct 530 ms 136656 KB Output is correct
19 Correct 1125 ms 164072 KB Output is correct
20 Correct 1089 ms 161528 KB Output is correct
21 Correct 1171 ms 164076 KB Output is correct
22 Correct 1158 ms 161508 KB Output is correct
23 Correct 1089 ms 161640 KB Output is correct
24 Correct 1115 ms 161656 KB Output is correct
25 Correct 1137 ms 161472 KB Output is correct
26 Correct 1143 ms 163988 KB Output is correct
27 Correct 1104 ms 164076 KB Output is correct
28 Correct 1093 ms 161452 KB Output is correct
29 Correct 1092 ms 161528 KB Output is correct
30 Correct 1119 ms 161656 KB Output is correct