Submission #1035956

#TimeUsernameProblemLanguageResultExecution timeMemory
1035956amine_arouaArranging Tickets (JOI17_arranging_tickets)C++17
0 / 100
0 ms348 KiB
#include<bits/stdc++.h> using namespace std; #define int long long struct Node { int sum , cnt; Node(){ sum = cnt = 0; } }; struct segTree { vector<Node> tree; int BASE; void build(int n) { BASE = n; while(__builtin_popcount(BASE) != 1) { BASE++; } tree.assign(4*BASE , Node()); } void upd(int node , int s , int e ,int l , int r , int val) { if(l > e || s > r) return ; if(l <= s && e <= r) { tree[node].cnt+=val; } else { int m = (s + e)>>1; upd(node<<1 , s , m , l , r , val); upd(node<<1|1 , m + 1 , e , l , r , val); } if(tree[node].cnt) { tree[node].sum = e - s + 1; } else tree[node].sum = tree[node<<1].sum + tree[node<<1|1].sum; } void upd(int l , int r , int val) { if(l > r) return; upd(1 , 0 , BASE - 1 , l , r , val); } }; void run_case() { int n , m; cin>>n>>m; segTree seg; seg.build(n); vector<int> in[n + 1] , out[n + 1]; for(int i = 0 ; i < m ; i++) { int a , b , c; cin>>a>>b>>c; a-- , b--; if(a > b) swap(a , b); in[a].push_back(b); out[b].push_back(a); seg.upd(a , b - 1 , 1); } int ans = n; for(int i = 0 ; i <= n ; i++) { ans = min(ans , seg.tree[1].sum); for(auto j : in[i]) { seg.upd(i , j - 1, -1); seg.upd(0 , i - 1 , 1); seg.upd(j , n - 1 , 1); } for(auto j : out[i]) { seg.upd(j , i - 1, 1); seg.upd(0 , j - 1 , -1); seg.upd(i , n - 1 , -1); } } cout<<ans<<'\n'; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin>>t; while (t--) { run_case(); } }
#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...