제출 #1257765

#제출 시각아이디문제언어결과실행 시간메모리
1257765efeg새로운 문제 (POI11_met)C++20
100 / 100
5877 ms59520 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define F first #define S second #define pb push_back #define endl '\n' #define all(v) v.begin(),v.end() #define gcd(a,b) __gcd(a,b) #define mt make_tuple #define pqueue priority_queue typedef pair<int,int> ii; typedef tuple<int,int,int> iii; typedef tuple<int,int,int,int> iiii; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<string> vs; typedef vector<char> vc; typedef vector<iii> viii; typedef set<int> si; typedef vector<ii> vii; typedef vector<vi> vvi; typedef vector<si> vsi; typedef vector<vb> vvb; typedef vector<vc> vvc; struct SegmentTree{ int n; vector<int> tree, lazy; SegmentTree(int _n){ n = _n; tree.assign(4*n + 5, 0); lazy.assign(4*n + 5, 0); } void push(int node,int s,int e){ if (lazy[node] == 0) return; tree[node] += lazy[node] * (e - s + 1); if (s != e){ lazy[node*2] += lazy[node]; lazy[node*2+1] += lazy[node]; } lazy[node] = 0; } void update(int node,int s,int e,int l,int r,int val){ push(node,s,e); if (s > e || r < s || e < l) return; if (l <= s && e <= r){ lazy[node] += val; push(node,s,e); return; } int m = (s+e)/2; update(node*2,s,m,l,r,val); update(node*2+1,m+1,e,l,r,val); tree[node] = tree[node*2] + tree[node*2+1]; } int query(int node,int s,int e,int x){ push(node,s,e); if (s > e || x < s || e < x) return 0; if (s == e && s == x) return tree[node]; int m = (s+e)/2; return query(node*2,s,m,x) + query(node*2+1,m+1,e,x); } }; int32_t main(){ ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); int n,m,k; cin >> n >> m; vi sec(m,0),gerekli(n,0); vvi devlet(n,vi()); for (int i = 0; i < m; i++){ cin >> sec[i]; sec[i]--; devlet[sec[i]].pb(i); } for (int i = 0; i < n; i++) cin >> gerekli[i]; cin >> k; viii queries(k+1); for (int i = 1; i <= k; i++){ int l,r,x; cin >> l >> r >> x; queries[i] = make_tuple(l-1,r-1,x); } vi left(n,1),right(n,k+1); int LOG = 0; while ((1LL << LOG) <= k) ++LOG; for (int iter = 0; iter < LOG; ++iter){ SegmentTree tree(m); vector<vi> check(k+2); for (int i = 0; i < n; ++i){ if (left[i] <= right[i] - 1){ int mid = (left[i] + right[i]) / 2; check[mid].pb(i); } } for (int t = 1; t <= k; ++t){ int a,b,val; tie(a,b,val) = queries[t]; if (a <= b){ tree.update(1, 0, m-1, a, b, val); } else { tree.update(1, 0, m-1, a, m-1, val); tree.update(1, 0, m-1, 0, b, val); } for (int state : check[t]){ long long sum = 0; for (int sec : devlet[state]){ sum += tree.query(1, 0, m-1, sec); if (sum >= gerekli[state]) break; } if (sum >= gerekli[state]){ right[state] = t; } else { left[state] = t + 1; } } } } for (int i = 0; i < n; i++){ if (left[i] == k+1) cout << "NIE" << endl; else cout << left[i] << endl; } return 0; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...