Submission #284923

#TimeUsernameProblemLanguageResultExecution timeMemory
284923achibasadzishviliDischarging (NOI20_discharging)C++14
0 / 100
995 ms242628 KiB
#include<bits/stdc++.h> #define ll long long #define f first #define s second #define pb push_back using namespace std; int n,a[1000002]; ll dp[1000002],rm[1000002][21],po[2000002],pw[200],raod,mn; int lef[1000002],rig[1000002]; vector<ll>del[1000002]; set<int>st; set<int>::iterator it; ll get(ll x,ll y){ ll lo = po[y - x + 1]; if(rm[y][lo] > rm[x + pw[lo] - 1][lo])return rm[y][lo]; return rm[x + pw[lo] - 1][lo]; } ll ind(ll x,ll y){ if(y == n)return -1; ll l = y + 1,r = n,mid,ind = -1; while(r >= l){ mid = (l + r) / 2; if(dp[x] + get(x + 1 , mid) * (n - x) >= dp[y] + get(y + 1 , mid) * (n - y)){ r = mid - 1; ind = mid; } else l = mid + 1; } return ind; } void delet(ll x){ if(lef[x] == rig[x] && lef[x] == -1)return; if(lef[x] == -1){ lef[rig[x]] = -1; mn = rig[x]; if(rig[x] == -1)while(1); rig[x] = -1; return; } rig[lef[x]] = rig[x]; lef[rig[x]] = lef[x]; ll cur = ind(lef[x] , rig[x]); if(cur == -1){ lef[x] = rig[x] = -1; return; } del[cur].pb(lef[x]); } int main(){ scanf("%d",&n); for(int i=1; i<=n; i++){ scanf("%d",&a[i]); } int cl = clock(); //n = 1000000; //for(int i=1; i<=n; i++) // a[i] = n-i+1; //pw[0] = 1; for(int i=1; i<=21; i++){ pw[i] = pw[i - 1] * 2; for(int j=pw[i - 1]; j<pw[i]; j++){ if(j <= 1000000) po[j] = i - 1; } } for(int i=0; i<=n; i++) lef[i] = rig[i] = -1; for(int i=1; i<=n; i++){ rm[i][0] = a[i]; for(int j=1; j<=20; j++){ if(i - pw[j] + 1 >= 1) rm[i][j] = max(rm[i][j - 1] , rm[i - pw[j - 1]][j - 1]); } } //cout << clock() - cl << '\n'; for(int i=1; i<=n; i++){ for(int j=0; j<del[i].size(); j++){ delet(del[i][j]); } dp[i] = dp[mn] + get(mn + 1 , i) * (n - mn); rig[i - 1] = i; lef[i] = i - 1; ll cur = ind(i - 1 , i); if(cur != -1) del[cur].pb(i - 1); } //cout << "time: " << clock() - cl << " " << raod << '\n'; cout << dp[n]; return 0; }

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int j=0; j<del[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~
Discharging.cpp:55:9: warning: unused variable 'cl' [-Wunused-variable]
   55 |     int cl = clock();
      |         ^~
Discharging.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Discharging.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |         scanf("%d",&a[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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...