oj.uz

Submission #253555

# Submission time Handle Problem Language Result Execution time Memory
253555 2020-07-28T09:15:33 Z SorahISA Bridges (APIO19_bridges) C++17
16 / 100
 768 ms 6392 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = priority_queue<T>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back
#define fastIO() ios_base::sync_with_stdio(false), cin.tie(0)

#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

struct Edge {
    int u, v, w;
};

const int maxn = 1 << 16;
const int INF = 0x7f7f7f7f;

int seg[maxn << 1];
/// single modify, range maximum ///

int Query(int qL, int qR, int id = 1, int nL = 0, int nR = maxn-1) {
    if (qL <= nL and nR <= qR) return seg[id];
    if (qR < nL or nR < qL) return INF; /// return any number > 10^9 ///
    
    int qM = qL + qR >> 1;
    int nM = nL + nR >> 1;
    return min(Query(qL, qR, ls(id), nL,     nM),
               Query(qL, qR, rs(id), nM + 1, nR));
}

int32_t main() {
    fastIO();
    
    int n, m, q;
    cin >> n >> m;
    
    vector<Edge> edge(m);
    for (auto &e : edge) cin >> e.u >> e.v >> e.w, --e.u, --e.v;
    for (int i = 0, j = maxn; i < m; ++i, ++j) seg[j] = edge[i].w;
    for (int j = maxn-1; j >= 1; --j) seg[j] = min(seg[ls(j)], seg[rs(j)]);
    
    cin >> q;
    
    for (int i = 1; i <= q; ++i) {
        int op, st, wi;
        cin >> op >> st >> wi;
        
        if (op == 1) {
            st += maxn - 1;
            seg[st] = wi;
            while (st >>= 1) seg[st] = min(seg[ls(st)], seg[rs(st)]);
        }
        if (op == 2) {
            --st;
            int ansL, ansR;
            
            int l = st, r = n-1, mi;
            while (l < r) {
                mi = l + r >> 1;
                if (Query(st, mi) >= wi) l = mi + 1;
                else r = mi;
            }
            ansR = l;
            
            l = -1, r = st-1;
            while (l < r) {
                mi = l + r + 1 >> 1;
                if (Query(mi, st-1) >= wi) r = mi - 1;
                else l = mi;
            }
            ansL = r;
            
            // cout << ansR << " " << ansL << " ";
            cout << ansR - ansL << "\n";
        }
    }
    
    return 0;
}

Compilation message

bridges.cpp: In function 'int64_t Query(int64_t, int64_t, int64_t, int64_t, int64_t)':
bridges.cpp:36:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int qM = qL + qR >> 1;
              ~~~^~~~
bridges.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int nM = nL + nR >> 1;
              ~~~^~~~
bridges.cpp:36:9: warning: unused variable 'qM' [-Wunused-variable]
     int qM = qL + qR >> 1;
         ^~
bridges.cpp: In function 'int32_t main()':
bridges.cpp:70:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                 mi = l + r >> 1;
                      ~~^~~
bridges.cpp:78:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                 mi = l + r + 1 >> 1;
                      ~~~~~~^~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 2552 KB Output is correct
2 Correct 403 ms 5368 KB Output is correct
3 Correct 399 ms 5240 KB Output is correct
4 Correct 405 ms 5368 KB Output is correct
5 Correct 422 ms 5368 KB Output is correct
6 Correct 453 ms 5496 KB Output is correct
7 Correct 437 ms 5240 KB Output is correct
8 Correct 477 ms 5240 KB Output is correct
9 Correct 40 ms 2424 KB Output is correct
10 Correct 413 ms 4248 KB Output is correct
11 Correct 439 ms 4248 KB Output is correct
12 Correct 768 ms 5372 KB Output is correct
13 Correct 132 ms 5240 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 389 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 6392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 2552 KB Output is correct
2 Correct 403 ms 5368 KB Output is correct
3 Correct 399 ms 5240 KB Output is correct
4 Correct 405 ms 5368 KB Output is correct
5 Correct 422 ms 5368 KB Output is correct
6 Correct 453 ms 5496 KB Output is correct
7 Correct 437 ms 5240 KB Output is correct
8 Correct 477 ms 5240 KB Output is correct
9 Correct 40 ms 2424 KB Output is correct
10 Correct 413 ms 4248 KB Output is correct
11 Correct 439 ms 4248 KB Output is correct
12 Correct 768 ms 5372 KB Output is correct
13 Correct 132 ms 5240 KB Output is correct
14 Incorrect 389 ms 2040 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -