Submission #1181727

#TimeUsernameProblemLanguageResultExecution timeMemory
1181727zadniprovskaFountain (eJOI20_fountain)C++20
30 / 100
77 ms14920 KiB
#include <bits/stdc++.h> using namespace std; #define el '\n' #define ll long long #define ld long double #define ull unsigned long long #define pll pair<long long, long long> #define ppll pair< long long, pair<long long, long long> > #define ff first #define ss second #define pb push_back #define pf push_front #define all(x) x.begin(), x.end() const ll DIM = 2e5+7; const ll INF = 1e18; const ll mod = 1e9 + 7; const ll maxlog = 20; struct Node { ll d, cap, id; }; Node a[DIM]; vector<pll> q[DIM]; ll answer[DIM], T[4*DIM]; bool cmp (Node t1, Node t2) { if (t1.d == t2.d) return t1.id < t2.id; return t1.d > t2.d; } void update(ll v, ll tl, ll tr, ll pos, ll val) { if (pos < tl || tr < pos) return; if (tl == tr) { T[v] = val; return; } ll tm = (tl + tr) >> 1; update(2*v+1, tl, tm, pos, val); update(2*v+2, tm+1, tr, pos, val); T[v] = T[2*v+1] + T[2*v+2]; } ll query1 (ll v, ll tl, ll tr, ll R) { if (R < tl) return 0; if (tr <= R) return T[v]; ll tm = (tl + tr) >> 1; return query1(2*v+1, tl, tm, R) + query1(2*v+2, tm+1, tr, R); } ll query2 (ll v, ll tl, ll tr, ll val) { if (tl == tr) return tl; ll tm = (tl + tr) >> 1; if (T[2*v+1] >= val) return query2(2*v+1, tl, tm, val); return query2(2*v+2, tm+1, tr, val - T[2*v+1]); } void solve() { ll n, nq; cin >> n >> nq; for (int i=1; i<=n; i++) { cin >> a[i].d >> a[i].cap; a[i].id = i; } sort(a+1, a+1+n, cmp); for (int i=1; i<=nq; i++) { ll pos, val; cin >> pos >> val; q[pos].pb({val, i}); } update(0, 1, n+1, n+1, INF); for (int i=1; i<=n; i++) { //cout << "/" << a[i].id << " " << a[i].d << " " << a[i].cap << el; update(0, 1, n+1, a[i].id, a[i].cap); for (auto [val, num] : q[a[i].id]) { ll bef; if (a[i].id != 1) bef = query1(0, 1, n+1, a[i].id-1); else bef = 0; ll res = query2(0, 1, n+1, bef+val); if (res == n+1) res = 0; answer[num] = res; } } for (int i=1; i<=nq; i++) { cout << answer[i] << el; } } signed main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); //freopen("nocross.in", "r", stdin); //freopen("nocross.out", "w", stdout); int ntest = 1; //cin >> ntest; while (ntest--){ solve(); } return 0; } ;
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...