제출 #1188740

#제출 시각아이디문제언어결과실행 시간메모리
1188740hyakupDistributing Candies (IOI21_candies)C++20
0 / 100
701 ms45620 KiB
#include "candies.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<long long, long long>; const int maxn = 2e5 + 10; const ll inf = 1e13; struct Evento{ int prior, id, val; Evento( int prior, int id, int val ) : prior(prior), id(id), val(val) {} bool operator < ( Evento e ){ return (( prior == e.prior ) ? abs(val) > abs(e.val) : prior < e.prior ); } }; class Segment_Tree{ private: struct Node{ pll mini, maxi; ll tot; Node(){ mini = pll( inf, 0 ); maxi = pll( -inf, 0 ); tot = 0; } Node( pll val ) : mini(val), maxi(val), tot(val.first) {} Node operator + ( Node n ){ Node resp; resp.mini = min( mini, pll( tot + n.mini.first, n.mini.second ) ); resp.maxi = max( maxi, pll( tot + n.maxi.first, n.maxi.second ) ); resp.tot = tot + n.tot; return resp; } }; vector<Node> seg; int n; void update( int pos, int ini, int fim, int id, int val ){ if( ini > id || id > fim ) return; if( ini == fim ){ seg[pos] = Node( pll( seg[pos].tot + val, ini ) ); return; } int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2; update( l, ini, mid, id, val ); update( r, mid + 1, fim, id, val ); seg[pos] = seg[l] + seg[r]; } Node query( int pos, int ini, int fim, int ki, int kf ){ if( ki > fim || ini > kf ) return seg[0]; if( ki <= ini && fim <= kf ) return seg[pos]; int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2; return query( l, ini, mid, ki, kf ) + query( r, mid + 1, fim, ki, kf ); } public: void update( int id, int val ){ update( 1, 0, n - 1, id, val ); } int query( ll val ){ int l = (( seg[1].mini.first <= 0 ) ? seg[1].mini.second + 1 : 0 ); int r = n - 1; if( l > r ) return 0; while( l < r ){ int mid = ( l + r + 1 )/2; Node x = query( 1, 0, n - 1, mid, n - 1 ); if( x.mini.first <= -val || x.maxi.first >= val || x.maxi.first - x.mini.first >= val ) l = mid; else r = mid - 1; } Node x = query( 1, 0, n - 1, r, n - 1 ); if( x.maxi.first >= val ) return val + query( 1, 0, n - 1, x.maxi.second + 1, n - 1 ).tot; return query( 1, 0, n - 1, x.mini.second + 1, n - 1 ).tot; } Segment_Tree( int n ) : n(n){ seg.resize(4*n); } }; vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v ){ int n = c.size(), q = l.size(); vector<Evento> line; for( int i = 0; i < n; i++ ) line.push_back( Evento( i, i, 0 ) ); for( int i = 0; i < q; i++ ){ line.push_back( Evento( l[i], i, v[i] ) ); line.push_back( Evento( r[i] + 1, i, -v[i] ) ); } sort( line.begin(), line.end() ); Segment_Tree seg(q); vector<int> resp(n); for( auto x : line ){ if( x.val != 0 ) seg.update( x.id, x.val ); else resp[x.id] = seg.query(c[x.id]); } return resp; }
#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...