Submission #284897

#TimeUsernameProblemLanguageResultExecution timeMemory
284897achibasadzishviliDischarging (NOI20_discharging)C++17
9 / 100
1114 ms242656 KiB
#include<bits/stdc++.h> #pragma GCC diagnostic warning "-std=c++11" #pragma GCC optimize("Ofast") #pragma GCC target("avx2,fma") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #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(rig[x] == -1){ rig[lef[x]] = -1; return; } if(lef[x] == -1){ lef[rig[x]] = -1; mn = rig[x]; 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]); if(lef[x] == mn)mn = rig[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] = i; 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:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
Discharging.cpp:7: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
Discharging.cpp:2:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    2 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~
Discharging.cpp: In function 'int main()':
Discharging.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int j=0; j<del[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~
Discharging.cpp:65:9: warning: unused variable 'cl' [-Wunused-variable]
   65 |     int cl = clock();
      |         ^~
Discharging.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Discharging.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |         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...