Submission #320622

#TimeUsernameProblemLanguageResultExecution timeMemory
320622vivaan_guptaDischarging (NOI20_discharging)C++14
100 / 100
374 ms16612 KiB
#include <bits/stdc++.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 #define int ll // 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 int MOD = 1e9+7; // 998244353; const int MX = 2e5+5; const ll INF = 1e18; // not too close to LLONG_MAX const ld PI = acos((ld)-1); const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; // for every grid problem!! mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); // helper funcs constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down 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; } #define tcTU tcT, class U 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; } tcT> void remDup(vector<T>& v) { // sort and remove duplicates sort(all(v)); v.erase(unique(all(v)),end(v)); } tcTU> void erase(T& t, const U& u) { // don't erase auto it = t.find(u); assert(it != end(t)); t.erase(u); } // element that doesn't exist from (multi)set // INPUT #define tcTUU tcT, class ...U tcT> void re(complex<T>& c); tcTU> void re(pair<T,U>& p); tcT> void re(vector<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(vector<T>& x) { trav(a,x) re(a); } tcT, size_t SZ> void re(AR<T,SZ>& x) { trav(a,x) re(a); } // TO_STRING #define ts to_string str ts(char c) { return str(1,c); } str ts(const char* s) { return (str)s; } str ts(str s) { return s; } str ts(bool b) { #ifdef LOCAL return b ? "true" : "false"; #else return ts((int)b); #endif } tcT> str ts(complex<T> c) { stringstream ss; ss << c; return ss.str(); } str ts(vector<bool> v) { str res = "{"; F0R(i,sz(v)) res += char('0'+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; } tcTU> str ts(pair<T,U> p); tcT> str ts(T v) { // containers with begin(), end() #ifdef LOCAL bool fst = 1; str res = "{"; for (const auto& x: v) { if (!fst) res += ", "; fst = 0; res += ts(x); } res += "}"; return res; #else bool fst = 1; str res = ""; for (const auto& x: v) { if (!fst) res += " "; fst = 0; res += ts(x); } return res; #endif } tcTU> str ts(pair<T,U> p) { #ifdef LOCAL return "("+ts(p.f)+", "+ts(p.s)+")"; #else return ts(p.f)+" "+ts(p.s); #endif } // OUTPUT tcT> void pr(T x) { cout << ts(x); } tcTUU> void pr(const T& t, const U&... u) { pr(t); pr(u...); } void ps() { pr("\n"); } // print w/ spaces tcTUU> void ps(const T& t, const U&... u) { pr(t); if (sizeof...(u)) pr(" "); ps(u...); } // DEBUG void DBG() { cerr << "]" << endl; } tcTUU> void DBG(const T& t, const U&... u) { cerr << ts(t); if (sizeof...(u)) cerr << ", "; DBG(u...); } #ifdef LOCAL // compile with -DLOCAL, chk -> fake assert #define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) #define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \ << __FUNCTION__ << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0); #else #define dbg(...) 0 #define chk(...) 0 #endif // FILE I/O void setIn(str s) { freopen(s.c_str(),"r",stdin); } void setOut(str s) { freopen(s.c_str(),"w",stdout); } void unsyncIO() { cin.tie(0)->sync_with_stdio(0); } void setIO(str 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 } const ll N = 1e6+5; int a[N]; int dp[N]; int calc(int i,int j){ int m = a[i]; FOR(k,i+1,j+1)m=max(m,a[k]); return m; } struct ConvexHullDynamic { // static const int INF=1e12; struct Line { int a, b; //y = ax + b double xLeft; //Stores the intersection wiith previous line in the convex hull. First line has -INF enum Type {line, maxQuery, minQuery} type; int val; explicit Line(int aa=0, int bb=0): a(aa), b(bb), xLeft(-INF), type(Type::line), val(0) {} int valueAt(int x) const { return a*x + b; } friend bool isParallel(const Line &l1, const Line &l2) { return l1.a == l2.a; } friend double intersectX(const Line &l1, const Line &l2) { return isParallel(l1, l2)?INF:1.0*(l2.b-l1.b)/(l1.a-l2.a); } bool operator<(const Line& l2) const { if(l2.type == line) return this->a < l2.a; if(l2.type == maxQuery) return this->xLeft < l2.val; if(l2.type == minQuery) return this->xLeft > l2.val; } }; bool isMax; set<Line> hull; bool hasPrev(set<Line>::iterator it) { return it!=hull.begin(); } bool hasNext(set<Line>::iterator it) { return it!=hull.end() && next(it)!=hull.end(); } bool irrelevant(const Line &l1, const Line &l2, const Line &l3) { return intersectX(l1, l3) <= intersectX(l1, l2); } bool irrelevant( set<Line>::iterator it) { return hasPrev(it) && hasNext(it) && ( (isMax && irrelevant(*prev(it), *it, *next(it))) || (!isMax && irrelevant(*next(it), *it, *prev(it)))); } //Updates xValue of line pointed by it set<Line>::iterator updateLeftBorder(set<Line>::iterator it) { if(isMax && !hasPrev(it) || !isMax && !hasNext(it)) return it; double val=intersectX(*it, isMax?(*prev(it)):(*next(it))); Line temp(*it); it=hull.erase(it); temp.xLeft=val; it=hull.insert(it, temp); return it; } explicit ConvexHullDynamic(bool isMax): isMax(isMax) {} void addLine(int a, int b) //Add ax + b in logN time { Line l3=Line(a, b); auto it=hull.lower_bound(l3); //If parallel liune is already in set, one of the lines becomes irrelevant if(it!=hull.end() && isParallel(*it, l3)) { if(isMax && it->b<b || !isMax && it->b>b) it=hull.erase(it); else return; } it=hull.insert(it, l3); if(irrelevant(it)) { hull.erase(it); return; } //Remove lines which became irrelevant after inserting while(hasPrev(it) && irrelevant(prev(it))) hull.erase(prev(it)); while(hasNext(it) && irrelevant(next(it))) hull.erase(next(it)); //Update xLine it=updateLeftBorder(it); if(hasPrev(it)) updateLeftBorder(prev(it)); if(hasNext(it)) updateLeftBorder(next(it)); } int getBest(int x) { Line q; q.val=x; q.type = isMax?Line::Type::maxQuery : Line::Type::minQuery; auto bestLine=hull.lower_bound(q); if(isMax) --bestLine; return bestLine->valueAt(x); } }; ConvexHullDynamic hull(0); signed main() { setIO(); // you should actually read the stuff at the bottom int n;re(n); FOR(i,1,n+1) re(a[i]); dp[0]= 0;// (dpval,cost) hull.addLine(n,dp[0]); int ma = 0; FOR(i,1,n+1){ ma = max(ma,a[i]); dp[i]=hull.getBest(ma); hull.addLine(n-i,dp[i]); } // FOR(i,1,n){ // ps(dp[i]); // } ps(dp[n]); } /* 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 */

Compilation message (stderr)

Discharging.cpp: In member function 'std::set<ConvexHullDynamic::Line>::iterator ConvexHullDynamic::updateLeftBorder(std::set<ConvexHullDynamic::Line>::iterator)':
Discharging.cpp:261:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  261 |         if(isMax && !hasPrev(it) || !isMax && !hasNext(it))
      |            ~~~~~~^~~~~~~~~~~~~~~
Discharging.cpp: In member function 'void ConvexHullDynamic::addLine(ll, ll)':
Discharging.cpp:281:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  281 |             if(isMax && it->b<b || !isMax && it->b>b)
      |                ~~~~~~^~~~~~~~~~
Discharging.cpp: In function 'void setIn(str)':
Discharging.cpp:182:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  182 | void setIn(str s) { freopen(s.c_str(),"r",stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Discharging.cpp: In function 'void setOut(str)':
Discharging.cpp:183:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  183 | void setOut(str s) { freopen(s.c_str(),"w",stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Discharging.cpp: In member function 'bool ConvexHullDynamic::Line::operator<(const ConvexHullDynamic::Line&) const':
Discharging.cpp:234:9: warning: control reaches end of non-void function [-Wreturn-type]
  234 |         }
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...