Submission #221461

#TimeUsernameProblemLanguageResultExecution timeMemory
221461patrikpavic2Constellation 3 (JOI20_constellation3)C++17
100 / 100
1158 ms126376 KiB
#include <cstdio> #include <vector> #include <map> #include <stack> #include <algorithm> #define PB push_back #define X first #define Y second using namespace std; typedef pair < int, int > pii; typedef vector < int > vi; typedef long long ll; const int N = 2e5 + 500; const int LOG = 18; map < int, ll > dp[N]; map < int, vi > sjec[N]; int n, m, kol[N]; int A[N], zvj[N], C[N]; int L[N], R[N], pos[N]; int rmq[N][LOG]; int par[N][2]; vector < pii > bitni; vi T[N][2]; int Q_L[N][2], Q_R[N][2], cur = 0; ll loga[N][2]; bool cmp(const pii &A,const pii &B){ return A.Y - A.X < B.Y - B.X; } void dfs(int x,int fl){ Q_L[x][fl] = cur++; for(int y : T[x][fl]) dfs(y, fl); Q_R[x][fl] = cur; } void add(int x,int fl, ll y){ for(x += 10; x < N ; x += x & -x) loga[x][fl] += y; } ll get(int x, int fl){ ll ret = 0; for(x += 10; x ; x -= x & -x) ret += loga[x][fl]; return ret; } inline int maax(int i,int j){ if(A[i] > A[j]) return i; return j; } inline int get_maax(int l,int r){ return maax(rmq[l][kol[r - l + 1]], rmq[r - (1 << kol[r - l + 1]) + 1][kol[r - l + 1]]); } ll svi_C = 0; ll f(int l,int r){ if(r < l) return 0; if(dp[l][r] != 0) return dp[l][r] - 1; int mks = get_maax(l, r); ll ret = f(l, mks - 1) + f(mks + 1, r); for(int x : sjec[l][r]) ret = max(ret, f(l, pos[x] - 1) + f(pos[x] + 1, r) + C[x]); dp[l][r] = ret + 1; return ret; } int main(){ scanf("%d", &n); vector < pii > saz; for(int i = 1;i <= n;i++){ scanf("%d", A + i); rmq[i][0] = i; } scanf("%d", &m); for(int i = 1;i <= n;i++) saz.PB({A[i], i + m}); for(int i = 0;i < m;i++){ scanf("%d%d%d", pos + i, zvj + i, C + i); saz.PB({zvj[i], i}); } sort(saz.begin(), saz.end()); for(int i = 0;i < n + m;i++){ if(saz[i].Y < m) zvj[saz[i].Y] = i + 1; else A[saz[i].Y - m] = i + 1; } A[0] = n + m + 1, A[n + 1] = n + m + 1; stack < int > s; s.push(0); for(int i = 1;i <= n;i++){ for(;A[s.top()] < A[i];s.pop()); par[i][0] = s.top(); s.push(i); if(par[i][0] < i - 1) bitni.PB({par[i][0] , i}); T[par[i][0]][0].PB(i); } bitni.PB({0, n + 1}); for(;!s.empty();s.pop()); s.push(n + 1); for(int i = n;i >= 1;i--){ for(;A[s.top()] < A[i];s.pop()); par[i][1] = s.top(); s.push(i); if(par[i][1] > i + 1) bitni.PB({i , par[i][1]}); T[par[i][1]][1].PB(i); } dfs(0, 0); cur = 0; dfs(n + 1, 1); for(int i = 1;i <= n + 2;i++){ {for(;(1 << kol[i]) <= i;kol[i]++); kol[i]--;} rmq[i][0] = i; } for(int j = 1;j < LOG;j++){ for(int i = 0;i <= n + 1;i++){ rmq[i][j] = rmq[i][j - 1]; if(i + (1 << (j - 1)) <= n + 1) rmq[i][j] = maax(rmq[i][j], rmq[i + (1 << (j - 1))][j - 1]); } } for(int i = 0;i < m;i++){ L[i] = pos[i], R[i] = pos[i]; for(int j = LOG - 1;j >= 0;j--){ if(L[i] - (1 << j) >= 1 && A[get_maax(L[i] - (1 << j), pos[i])] < zvj[i]) L[i] -= (1 << j); if(R[i] + (1 << j) <= n && A[get_maax(pos[i], R[i] + (1 << j))] < zvj[i]) R[i] += (1 << j); } L[i]--, R[i]++; sjec[L[i]][R[i]].PB(i); svi_C += C[i]; } sort(bitni.begin(), bitni.end(), cmp); for(pii ja : bitni){ int l = ja.X, r = ja.Y; int mks = get_maax(l + 1, r - 1); ll cur = dp[l][mks] + dp[mks][r]; for(int x : sjec[l][r]){ cur = max(cur, (ll)C[x] + get(Q_L[pos[x]][0], 0) + get(Q_L[pos[x]][1], 1) - get(Q_L[l][0], 0) - get(Q_L[r][1], 1)); } dp[l][r] = cur; if(A[l] > A[r]){ add(Q_L[r][0], 0, cur); add(Q_R[r][0], 0, -cur); } if(A[l] < A[r]){ add(Q_L[l][1], 1, cur); add(Q_R[l][1], 1, -cur); } } printf("%lld\n", svi_C - dp[0][n + 1]); }

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
constellation3.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A + i);
   ~~~~~^~~~~~~~~~~~~
constellation3.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
constellation3.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", pos + i, zvj + i, C + i); 
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...