Submission #284988

#TimeUsernameProblemLanguageResultExecution timeMemory
284988achibasadzishviliDischarging (NOI20_discharging)C++17
0 / 100
759 ms153208 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]; int rm[1000002][21],po[2000002],pw[200],raod,mn,lo; int lef[1000002],rig[1000002]; vector<int>del[1000002]; int get(int x,int y){ return a[y]; 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]; } int ind(int x,int 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(int x){ if(lef[x] == rig[x] && lef[x] == -1)return; if(lef[x] == -1){ lef[rig[x]] = -1; mn = rig[x]; rig[x] = -1; return; } rig[lef[x]] = rig[x]; lef[rig[x]] = lef[x]; int cur = ind(lef[x] , rig[x]); if(cur == -1){ lef[x] = rig[x] = -1; return; } del[cur].pb(lef[x]); lef[x] = rig[x] = -1; } 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++){ rm[i][j] = rm[i][j - 1]; if(i - pw[j] + 1 >= 1 && rm[i - pw[j - 1]][j - 1]>rm[i][j]) rm[i][j] = 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] + (ll)get(mn + 1 , i) * (ll)(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:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int j=0; j<del[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~
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...