Submission #284881

#TimeUsernameProblemLanguageResultExecution timeMemory
284881achibasadzishviliDischarging (NOI20_discharging)C++17
0 / 100
924 ms262704 KiB
#include<bits/stdc++.h> #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; vector<ll>del[1000002]; set<ll>st; set<ll>::iterator it; ll get(ll x,ll y){ return 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){ raod++; it = st.find(x); if(it == st.end())return; st.erase(it); it = st.upper_bound(x); if(it == st.end() || it == st.begin())return; ll y = (*it); it--; x = (*it); ll cur = ind(x , y); if(cur == -1)return; del[cur].pb(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] = 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=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'; st.insert(0); for(int i=1; i<=n; i++){ for(int j=0; j<del[i].size(); j++){ delet(del[i][j]); } ll x = (*st.begin()); dp[i] = dp[x] + get(x + 1 , i) * (n - x); it = st.end(); it--; st.insert(i); ll cur = ind((*it) , i); if(cur != -1) del[cur].pb((*it)); } //cout << "time: " << clock() - cl << " " << raod << '\n'; cout << dp[n]; return 0; }

Compilation message (stderr)

Discharging.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
Discharging.cpp:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
Discharging.cpp: In function 'int main()':
Discharging.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for(int j=0; j<del[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~
Discharging.cpp:56:9: warning: unused variable 'cl' [-Wunused-variable]
   56 |     int cl = clock();
      |         ^~
Discharging.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Discharging.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |         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...