Submission #496331

#TimeUsernameProblemLanguageResultExecution timeMemory
496331IerusMeteors (POI11_met)C++17
24 / 100
6099 ms7752 KiB
#include<bits/stdc++.h> /* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; */ using namespace std; #pragma GCC optimize ("unroll-loops,Ofast,O3") #pragma GCC target("avx,avx2,fma") #define F first #define S second #define sz(x) (int)x.size() #define pb push_back #define eb emplace_back #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ; #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) //#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> typedef long long ll; const int E = 1e9; const long long inf = 1e18+777; const int N = 3e5+777; const int MOD = 1e9+7; const bool I = 1; int n, m, o[N], p[N], l[N], r[N], a[N], que; bool check(int Do, int pos){ // cerr << "M: " << Do << " pos: " << pos << '\n'; vector<int> pr(m+3, 0); for(int i = 1; i <= Do; ++i){ if(l[i] > r[i]){ pr[l[i]] += a[i]; pr[m+1] -= a[i]; pr[1] += a[i]; pr[r[i]+1] -= a[i]; }else{ pr[l[i]] += a[i], pr[r[i]+1] -= a[i]; } } // cerr << "Pr1\n"; // for(int i = 1; i <= m; ++i){ // cout << pr[i] << ' '; // }cerr << '\n'; int res = 0; for(int i = 1; i <= m; ++i){ pr[i] += pr[i-1]; if(o[i] == pos){ res += pr[i]; } } // cerr << "Pr2\n"; // for(int i = 1; i <= m; ++i){ // cerr << pr[i] << ' '; // }cerr << '\n'; return (res >= p[pos]); } vector<int> ans(N, -1); signed main(){NFS; cin >> n >> m; for(int i = 1; i <= m; ++i){ cin >> o[i]; } for(int i = 1; i <= n; ++i){ cin >> p[i]; } cin >> que; for(int i = 1; i <= que; ++i){ cin >> l[i] >> r[i] >> a[i]; } for(int i = 1; i <= n; ++i){ int L = 1, R = que , res = -1; while(L <= R){ int M = (L + R) >> 1; if(check(M, i)){ R = (res = M) - 1; }else L = M + 1; } ans[i] = res; // cerr << "i: " << res << '\n'; // exit(false); } for(int i = 1; i <= n; ++i){ if(ans[i] == -1) cout << "NIE\n"; else cout << ans[i] << '\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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...