# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
130537 | 2019-07-15T13:28:22 Z | wilwxk | Bridges (APIO19_bridges) | C++14 | 1862 ms | 8952 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN=5e4+5; const int INF=1e9+9; const int SQRN=4; vector<pair<int, int> > g[MAXN]; int weight[MAXN]; int mn[MAXN], bini[MAXN], bfim[MAXN]; int n, m, q; void precalc() { fill(bini, bini+m, MAXN); fill(mn, mn+m, INF); for(int i=0; i<m; i++) { bini[i/SQRN]=min(bini[i/SQRN], i); bfim[i/SQRN]=max(bfim[i/SQRN], i); } } void update(int ind, int val) { weight[ind]=val; int bind=ind/SQRN; if(val<=mn[bind]) { mn[bind]=val; return; } mn[bind]=val; for(int i=bini[bind]; i<=bfim[bind]; i++) mn[bind]=min(mn[bind], weight[i]); } int query(int cur, int val) { int resp=1; for(int i=cur; i<m; i++) { int bind=i/SQRN; if(weight[i]<val) break; if(mn[bind]>=val) resp+=(bfim[bind]-i+1), i=bfim[bind]; else resp++; } // for(int i=0; i<=n/SQRN; i++) printf("%d >> %d %d >> %d\n", i, bini[i], bfim[i], mn[i]); // printf("qu %d %d >> %d\n", cur, val, resp); for(int i=cur-1; i>=0; i--) { int bind=i/SQRN; if(weight[i]<val) break; if(mn[bind]>=val) resp+=(i-bini[bind]+1), i=bini[bind]; else resp++; } return resp; } int main() { scanf("%d %d", &n, &m); precalc(); for(int i=0; i<m; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); a--; b--; g[a].push_back({b, i}); g[b].push_back({a, i}); weight[i]=c; } for(int i=0; i<m; i++) update(i, weight[i]); scanf("%d", &q); while(q--) { int a, b, c; scanf("%d %d %d", &a, &b, &c); if(a==1) update(b-1, c); else printf("%d\n", query(b-1, c)); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 1528 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 76 ms | 6516 KB | Output is correct |
2 | Correct | 78 ms | 6520 KB | Output is correct |
3 | Correct | 76 ms | 6520 KB | Output is correct |
4 | Correct | 90 ms | 6652 KB | Output is correct |
5 | Correct | 91 ms | 6620 KB | Output is correct |
6 | Correct | 1862 ms | 6696 KB | Output is correct |
7 | Correct | 1114 ms | 6808 KB | Output is correct |
8 | Correct | 761 ms | 6704 KB | Output is correct |
9 | Correct | 45 ms | 3064 KB | Output is correct |
10 | Correct | 1454 ms | 5856 KB | Output is correct |
11 | Correct | 995 ms | 5752 KB | Output is correct |
12 | Correct | 1454 ms | 6712 KB | Output is correct |
13 | Correct | 217 ms | 6520 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 67 ms | 5624 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 42 ms | 8952 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 76 ms | 6516 KB | Output is correct |
2 | Correct | 78 ms | 6520 KB | Output is correct |
3 | Correct | 76 ms | 6520 KB | Output is correct |
4 | Correct | 90 ms | 6652 KB | Output is correct |
5 | Correct | 91 ms | 6620 KB | Output is correct |
6 | Correct | 1862 ms | 6696 KB | Output is correct |
7 | Correct | 1114 ms | 6808 KB | Output is correct |
8 | Correct | 761 ms | 6704 KB | Output is correct |
9 | Correct | 45 ms | 3064 KB | Output is correct |
10 | Correct | 1454 ms | 5856 KB | Output is correct |
11 | Correct | 995 ms | 5752 KB | Output is correct |
12 | Correct | 1454 ms | 6712 KB | Output is correct |
13 | Correct | 217 ms | 6520 KB | Output is correct |
14 | Incorrect | 67 ms | 5624 KB | Output isn't correct |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 1528 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |