Submission #1203433

#TimeUsernameProblemLanguageResultExecution timeMemory
1203433trandangquangArranging Tickets (JOI17_arranging_tickets)C++20
0 / 100
2 ms4928 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=200005; int n,m,p,a[N],pre[N],f[N]; ll add; vector<int> seg[N]; bool chk(int x, int y){ FOR(i,1,n) f[i]=0; int val=a[p]-(x-y); FOR(i,1,n) pre[i]=max(0,(a[i]+val-x+1)/2); priority_queue<ii> pq; int cur=0; FOR(l,1,p){ for(int r:seg[l]) pq.emplace(r,l); while(cur<pre[l]){ if(pq.empty()) break; auto [rs,ls]=pq.top(); pq.pop(); f[ls]++; f[rs+1]--; } } if(pre[x]!=val) return false; FOR(i,1,n){ f[i]+=f[i-1]; if(f[i]<pre[i]) 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); if(c&1){ seg[l].eb(r); a[l]++; a[r+1]--; } add+=c/2; } p=1; FOR(i,1,n){ a[i]+=a[i-1]; if(a[i]>a[p]) p=i; } int L=0, R=n, res=-1; while(L<=R){ int M=(L+R)>>1; if(chk(M,0)||chk(M,1)){ res=M; R=M-1; } else{ L=M+1; } } cout<<res+add<<'\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...