Submission #388440

#TimeUsernameProblemLanguageResultExecution timeMemory
388440ACmachineWall (IOI14_wall)C++17
100 / 100
1177 ms74208 KiB
#include "wall.h" #include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in) #define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in) #define REP(i,b) FOR(i,0,b,1) #define REPD(i,b) FORD(i,b,0,1) #define pb push_back #define mp make_pair #define ff first #define ss second #define all(x) begin(x), end(x) #define MANY_TESTS int tcase; cin >> tcase; while(tcase--) const double EPS = 1e-9; const int MOD = 1e9+7; const ll INFF = 1e18; const int INF = 1e9; const ld PI = acos((ld)-1); const vi dy = {1, 0, -1, 0, -1, 1, 1, -1}; const vi dx = {0, 1, 0, -1, -1, 1, -1, 1}; void DBG(){cout << "]" << endl;} template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); } #define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__); #define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl; template<class T, unsigned int U> ostream& operator<<(ostream& out, const array<T, U> &v){out << "["; REP(i, U) out << v[i] << ", "; out << "]"; return out;} template <class T, class U> ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;} template <class T> ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; } template <class T, class U> ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; } template<class T> ostream& operator<<(ostream& out, const vector<T> &v){ out << "["; REP(i, v.size()) out << v[i] << ", "; out << "]"; return out;} template<class T> istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; } // on segtree[TIME] is operation information // I toggle operations as I scanline int n, k; vector<int> op, height; struct node{ bool Sop = false; int S = -1, D = INF, I = -1; void apply(int _D, int _I){ Sop = false; D = _D; I = _I; } }; struct segtree{ node comb(const node& a, const node& b){ node res; if(b.Sop){res = b; return res;} res = a; // will be overwritten if(res.Sop){ res.S = max(res.S, b.I); res.S = min(res.S, b.D); return res; } res.I = max(res.I, b.I); res.D = min(res.D, b.D); if(res.D <= res.I){ res.Sop = true; res.S = ((res.I == b.I) ? res.I : res.D); } return res; } int n; vector<node> tree; segtree(int _n){ n = 1; while(n < _n) n*= 2; tree.resize(2 * n); } void upd(int pos, int state){ int _D, _I; if(state == 1){ if(op[pos] == 1){_I = height[pos]; _D = INF;} else{_I = -1; _D = height[pos];} } else{ _D = INF; _I = -1; } pos += n; tree[pos].apply(_D, _I); for(int i = pos / 2; i > 0; i/=2) tree[i] = comb(tree[i<<1], tree[i<<1|1]); } int query(int value){ //what it gets transformed to if(tree[1].Sop) return tree[1].S; value = max(value, tree[1].I); value = min(value, tree[1].D); return value; } }; void buildWall(int N, int K, int OP[], int LEFT[], int RIGHT[], int HEIGHT[], int finalHeight[]){ n = N; k = K; op.resize(K); height.resize(K); REP(i, k){ op[i] = OP[i]; height[i] = HEIGHT[i]; } segtree st(k); vector<array<int, 2>> ev(k); REP(i, k) ev[i] = {LEFT[i], i}; sort(all(ev)); int pp = 0; set<pair<int, int>> open; REP(i, n){ while(pp < ev.size() && ev[pp][0] <= i){ st.upd(ev[pp][1], 1); open.insert({RIGHT[ev[pp][1]], ev[pp][1]}); pp++; } while(!open.empty() && open.begin()->ff < i){ st.upd(open.begin()->ss, 0); open.erase(open.begin()); } finalHeight[i] = st.query(0); } return; }

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:130:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         while(pp < ev.size() && ev[pp][0] <= i){
      |               ~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...