Submission #862068

#TimeUsernameProblemLanguageResultExecution timeMemory
862068guagua0407Two Dishes (JOI19_dishes)C++17
0 / 100
10073 ms102616 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); void setIO(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } const int mxn=1e6+5; ll a[mxn],S[mxn],Q[mxn]; ll b[mxn],T[mxn],P[mxn]; int pa[mxn],pb[mxn]; ll g[mxn],V[mxn]; vector<int> qa[mxn],qb[mxn]; int n,m; int main() {_ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]>>S[i]>>P[i]; a[i]+=a[i-1]; } for(int i=1;i<=m;i++){ cin>>b[i]>>T[i]>>Q[i]; b[i]+=b[i-1]; } for(int i=1;i<=n;i++){ int pos=upper_bound(b,b+m+1,S[i]-a[i])-b-1; pa[i]=pos; if(pos>=0) qa[pos].push_back(i); } for(int i=1;i<=m;i++){ int pos=upper_bound(a,a+n+1,T[i]-b[i])-a-1; pb[i]=pos; if(pos>=0) qb[pos].push_back(i); } for(int i=1;i<=m;i++){ if(pb[i]>=0) g[i]=V[i]=Q[i]; } set<int> S; vector<int> vec; S.insert(m+1); V[m+1]=-1e18; for(int i=1;i<=n;i++){ if(pa[i]>=0){ g[0]+=P[i]; g[pa[i]+1]-=P[i]; if(pa[i]+1<=m) S.insert(pa[i]+1); if(g[pa[i]+1]<V[pa[i]+1]){ if(pa[i]+1<=m) vec.push_back(pa[i]+1); } } for(auto v:qb[i-1]){ if(g[v]>0 or g[v]<0){ S.insert(v); } if(g[v]<0){ vec.push_back(v); } V[v]=0; } sort(all(vec)); for(auto v:vec){ auto it=S.lower_bound(v); if(*it!=v) continue; while(it!=S.end()){ int cur=*it; ll dif=V[cur]-g[cur]; int nxt=*next(it); g[cur]=V[cur]; g[nxt]-=dif; if(g[nxt]>=V[nxt]){ S.erase(it); if(g[nxt]==V[nxt]) S.erase(S.find(nxt)); break; } else{ it=S.erase(it); } } } } for(int i=1;i<=m;i++){ g[i]+=g[i-1]; } cout<<g[m]<<'\n'; return 0; } //maybe its multiset not set

Compilation message (stderr)

dishes.cpp: In function 'void setIO(std::string)':
dishes.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((s + ".out").c_str(), "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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...