Submission #1203438

#TimeUsernameProblemLanguageResultExecution timeMemory
1203438trandangquangArranging Tickets (JOI17_arranging_tickets)C++20
85 / 100
6094 ms12228 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i <= (b); ++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define sz(a) (int)(a).size() #define all(a) (a).begin(), (a).end() #define bit(s, i) (((s) >> (i)) & 1) #define ii pair <int, int> #define fi first #define se second #define ll long long #define eb emplace_back #define pb push_back #define __builtin_popcount __builtin_popcountll template <class X, class Y> bool maximize(X &x, Y y) { if(x < y) { x = y; return true; } return false; } template <class X, class Y> bool minimize(X &x, Y y) { if(x > y) { x = y; return true; } return false; } void solve(); int32_t main() { #define task "test" if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } cin.tie(0)->sync_with_stdio(0); int tc = 1; //cin >> tc; FOR(i, 1, tc){ solve(); } } const int N=2e5+5; int n,m,p; ll a[N],s[N]; vector<ii> seg[N]; bool chk(ll mxB, ll M){ FOR(i,1,n) s[i]=0; priority_queue<ii> pq; ll cur=0; FOR(i,1,p){ ll need=(a[i]+mxB-M+1)/2; for(auto [x,y]:seg[i]){ if(x>p){ pq.push({x,y}); } } while(cur<need){ if(pq.empty()) return false; auto [x,y]=pq.top(); pq.pop(); if(cur+y<=need){ cur+=y; s[x]+=y; } else{ s[x]+=need-cur; pq.push({x,y-(need-cur)}); cur=need; } } } FOR(i,p+1,n){ cur-=s[i]; ll need=(a[i]+mxB-M+1)/2; if(cur<need) return false; } return true; } void solve() { cin>>n>>m; FOR(i,1,m){ int l,r,c; cin>>l>>r>>c; if(l>r) swap(l,r); a[l]+=c; a[r]-=c; seg[l].eb(r,c); } p=1; FOR(i,1,n){ a[i]+=a[i-1]; if(a[i]>a[p]) p=i; } ll L=1, R=1e14, res=0; while(L<=R){ int M=(L+R)>>1; if(chk(a[p]-M,M)||chk(a[p]-M+1,M)){ res=M; R=M-1; } else{ L=M+1; } } cout<<res<<'\n'; }

Compilation message (stderr)

arranging_tickets.cpp: In function 'int32_t main()':
arranging_tickets.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
arranging_tickets.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         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...