제출 #886531

#제출 시각아이디문제언어결과실행 시간메모리
886531vjudge1Gym Badges (NOI22_gymbadges)C++17
100 / 100
991 ms59644 KiB
#include <bits/stdc++.h> using namespace std; #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #define fastio() cin.tie(0), ios_base::sync_with_stdio(0) #define sp " " #define endl "\n" #define pb push_back #define pii pair<int, int> #define st first #define nd second #define N 500005 #define int long long #define L(node) node * 2 #define R(node) node * 2 + 1 const int INF = 1e9 + 7; int x[N], l[N], lazy[4 * N], tree[4 * N], ind[N]; int mini[4 * N]; void push(int node, int l, int r){ mini[node] += lazy[node]; if (l != r){ lazy[L(node)] += lazy[node]; lazy[R(node)] += lazy[node]; } lazy[node] = 0; } void sett(int node, int l, int r, int sl, pii val){ push(node, l, r); if (l > sl || r < sl) return; if (l == r){ if (l == sl){ tree[node] = val.nd; mini[node] = val.st; } return; } int mid = (l + r) / 2; sett(L(node), l, mid, sl, val); sett(R(node), mid + 1, r, sl, val); tree[node] = tree[L(node)] + tree[R(node)]; mini[node] = min(mini[L(node)], mini[R(node)]); } void update(int node, int l, int r, int sl, int sr, int val){ push(node, l, r); if (l > r || l > sr || r < sl) return; if (l >= sl && r <= sr){ lazy[node] += val; push(node, l, r); return; } int mid = (l + r) / 2; update(L(node), l, mid, sl, sr, val); update(R(node), mid + 1, r, sl, sr, val); mini[node] = min(mini[L(node)], mini[R(node)]); } int pos_query(int node, int l, int r, int val){ push(node, l, r); if (l == r){ if (mini[node] >= val) return l; return INF; } int mid = (l + r) / 2; push(L(node), l, mid); push(R(node), mid + 1, r); if (mini[R(node)] < val) return pos_query(R(node), mid + 1, r, val); return min(pos_query(L(node), l, mid, val), mid + 1); } int query(int node, int l, int r, int sl, int sr){ push(node, l, r); if (l > r ||l > sr || r < sl) return 0; if (l >= sl && r <= sr) return tree[node]; int mid = (l + r) / 2; return query(L(node), l, mid, sl, sr) + query(R(node), mid + 1, r, sl, sr); } int min_query(int node, int l, int r, int sl, int sr){ push(node, l, r); if (l > r ||l > sr || r < sl) return INF; if (l >= sl && r <= sr) { return mini[node]; } int mid = (l + r) / 2; int ans = min(min_query(L(node), l, mid, sl, sr), min_query(R(node), mid + 1, r, sl, sr)); return ans; } void build(int node, int l, int r){ mini[node] = INF; tree[node] = 0; if (l == r) return; int mid = (l + r) / 2; build(L(node), l, mid); build(R(node), mid + 1, r); } int32_t main(){ //fileio(); fastio(); int n; cin>>n; build(1, 1, n); for (int i = 1; i <= n; i++){ cin>>x[i]; } for (int i = 1; i <= n; i++){ cin>>l[i]; } vector<int> v(n, 0), g(n , 0); iota(v.begin(), v.end(), 1); iota(g.begin(), g.end(), 1); sort(v.begin(), v.end(), [&](int a, int b){ if (x[a] == x[b]) return l[a] < l[b]; return x[a] < x[b]; }); sort(g.begin(), g.end(), [&](int a, int b){ if (x[a] + l[a] == x[b] + l[b]) return x[a] < x[b]; return x[a] + l[a] < x[b] + l[b]; }); for (int i = 0; i < n; i++){ ind[g[i]] = i + 1; } int sum = 0; int ans = 0; for (auto i : v){ //check int pos = pos_query(1, 1, n, sum + x[i]); if (l[i] >= sum - query(1, 1, n, pos, n)){ int first = x[i] + l[i] + query(1, 1, n, ind[i] + 1, n); int second = x[i]; sett(1, 1, n, ind[i], {first, second}); update(1, 1, n, 1, ind[i] - 1, second); ans++; sum += x[i]; } } //cout<<endl; cout<<ans<<endl; cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...