Submission #1274750

#TimeUsernameProblemLanguageResultExecution timeMemory
1274750sasdeFlooding Wall (BOI24_wall)C++20
70 / 100
5089 ms16220 KiB
#include<bits/stdc++.h> using namespace std; bool M1; #define PI 3.14159265358979323846 #define sz(a) (int)a.size() #define all(x) x.begin(),x.end() #define ii pair<int,int> #define iii pair<int,ii> #define iv pair<ii,ii> #define se second #define fi first #define ffi fi.fi #define sfi se.fi #define sse se.se #define fse fi.se #define lt(i, c, d) for(int i = c; i <= d; ++i) #define fl(i, c, d) for(int i = d; i >= c; --i) #define pb push_back #define emb emplace_back #define emf emplace_front #define em emplace #define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n' #define look_time cerr << "TIME : " << clock() * 0.001 << "s" <<'\n' const int N=1e6+5,lg=30,mod=1e9+7; mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); int Rand(int u,int v){ return u+rd()%(v-u+1); } int dx[]={1,0,-1,0,1,1,-1,-1}; int dy[]={0,-1,0,1,1,-1,1,-1}; int node,a[N],b[N],ans,po[N],w[N],pre[N],suf[N]; vector<int>nen; int tru(int u,int v){ u-=v; if(u<0)u+=mod; return u; } int ne(int u){ return lower_bound(all(nen),u)-nen.begin()+1; } bool M2; void solve(){ cin >> node; po[0]=1; nen.emb(0); for(int i=1;i<=node;++i){ cin >> a[i]; nen.emb(a[i]); po[i]=2LL*po[i-1]%mod; } for(int i=1;i<=node;++i){ cin >> b[i]; nen.emb(b[i]); } sort(all(nen)); nen.erase(unique(all(nen)),nen.end()); int n=sz(nen); pre[0]=suf[node+1]=1; for(int i=1;i<n;++i){ for(int j=1;j<=node;++j){ w[j]=(nen[i]>a[j])+(nen[i]>b[j]); pre[j]=1LL*pre[j-1]*w[j]%mod; } for(int j=node;j>=1;--j){ suf[j]=1LL*suf[j+1]*w[j]%mod; } int val=0; for(int j=2;j<node;++j){ val=(val+1LL*w[j]*tru(po[j-1],pre[j-1])%mod*tru(po[node-j],suf[j+1])%mod)%mod; // cout <<w[j]<<" "<<po[j-1]<<" "<<pre[j-1]<<" "<<po[node-j]<<" "<<suf[j+1]<<'\n'; } ans=(ans+1LL*val*tru(nen[i],nen[i-1])%mod)%mod; } cout << ans; } main() { srand(time(0)); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define task "aws" if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } int t=1; // cin >> t; while(t--){ solve();cout<<'\n'; } look_memory; look_time; }

Compilation message (stderr)

Main.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:85:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:86:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...