Submission #284967

#TimeUsernameProblemLanguageResultExecution timeMemory
284967achibasadzishviliDischarging (NOI20_discharging)C++14
0 / 100
397 ms258768 KiB
#include<bits/stdc++.h> #define ll long long #define f first #define s second #define pb push_back using namespace std; ll n,a[1000002]; ll dp[1000002],rm[1000002][21],po[2000002],pw[200],raod,mn; ll lef[1000002],rig[1000002]; vector<ll>del[1000002]; ll get(ll x,ll y){ return a[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]; 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]); 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<=19; 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:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(int j=0; j<del[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~
#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...