| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 865161 |
2023-10-24T06:09:45 Z |
vjudge1 |
Meteors (POI11_met) |
C++17 |
|
6000 ms |
17240 KB |
#include <bits/stdc++.h>
#define pb push_back
#define all(q) q.begin (), q.end ()
#define ll long long
#define f first
#define s second
using namespace std;
const ll MOD = 1e9 + 7;
const ll inf = 1e9 + 1;
const ll INF = 1e18 + 1;
const ll N = 2e6 + 1;
const int k = 15;
int u[N], o[N], p[N], t[N], ans[N];
void push (int v, int l, int r){
if (l != r && u[v]){
u[v + v] += u[v];
u[v + v + 1] += u[v];
int mid = (l + r) / 2;
t[v + v] += (mid - l + 1) * u[v];
t[v + v + 1] += (r - mid) * u[v];
u[v] = 0;
}
}
void upd (int v, int l, int r, int tl, int tr, int x){
push (v, l, r);
if (tl <= l && r <= tr){
u[v] += x;
t[v] += x * (r - l + 1);
push(v, l, r);
return;
}
if (l > tr || tl > r) return;
ll mid = (l + r) / 2;
upd (v + v, l, mid, tl, tr, x);
upd (v + v + 1, mid + 1, r, tl, tr, x);
t[v] = t[v + v] + t[v + v + 1];
}
ll get (int v, int l, int r, int tl, int tr){
if (tl > r || l > tr) {/*cout << 3 << l << ' ' << r << '\n';*/ return 0ll;}
if (tl <= l && r <= tr){
// cout << 1 << l << ' ' << r << '\n';
push (v, l, r);
return t[v];
}
push (v, l, r);
int mid = (l + r) / 2;
return get (v + v, l, mid, tl, tr) + get (v + v + 1, mid + 1, r, tl, tr);
}
void solve (){
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i){
cin >> o[i];
}
for (int i = 1; i <= n; ++i){
cin >> p[i];
}
int k, ti = 0;
cin >> k;
while (k--){
++ti;
int l, r, x;
cin >> l >> r >> x;
if (l <= r){
upd (1, 1, m, l, r, x);
// for (int i = 1; i <= 9; ++i) cout << t[i] << ' ';
// cout << '\n';
}
else {
upd (1, 1, m, l, m, x);
upd (1, 1, m, 1, r, x);
// for (int i = 1; i <= 9; ++i) cout << t[i] << ' ';
// cout << '\n';
}
vector <ll> a (n + 1, 0);
for (int i = 1; i <= m; ++i){
ll q = get (1, 1, m, i, i);
a[o[i]] += q;
}
for (int i = 1; i <= n; ++i){
if (a[i] >= p[i] && !ans[i]) ans[i] = ti;
}
}
for (int i = 1; i <= n; ++i){
if (ans[i]) cout << ans[i] << '\n';
else cout << "NIE\n";
}
}
main (){
ios_base::sync_with_stdio (0);
cin.tie (0);
// freopen("guard.in", "r", stdin);
// freopen("guard.out", "w", stdout);
ll t = 1;
// cin >> t;
for (ll i = 1; i <= t; ++i){
// cout << "Case " << i << ':' << '\n';
solve ();
// cout << '\n';
}
}
Compilation message
met.cpp:97:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
97 | main (){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
84 ms |
6612 KB |
Output is correct |
| 3 |
Correct |
126 ms |
6612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
6616 KB |
Output is correct |
| 2 |
Correct |
76 ms |
6616 KB |
Output is correct |
| 3 |
Correct |
84 ms |
6488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6030 ms |
7148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6040 ms |
7472 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6034 ms |
7180 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6017 ms |
7000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6004 ms |
17240 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6004 ms |
17164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
