oj.uz

답안 #240143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
240143 2020-06-18T07:32:56 Z wiwiho 다리 (APIO19_bridges) C++14
16 / 100
 1422 ms 5404 KB 
//#define NDEBUG

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) ((a + b - 1) / b)
#define tomax(a, b) (a = max(a, b))
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

//#define TEST

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

struct Node{
    int v = 0, l = -1, r = -1;
};

vector<Node> st;
int ts = 0;
vector<int> w;
int m;

int build(int l, int r){
    int id = ts++;
    cerr << id << "\n";
    if(l == r){
        st[id].v = w[l];
        return id;
    }
    int m = (l + r) / 2;
    st[id].l = build(l, m);
    st[id].r = build(m + 1, r);
    st[id].v = min(st[st[id].l].v, st[st[id].r].v);
    return id;
}

void modify(int x, int v, int L, int R, int id){
    if(L == R){
        st[id].v = v;
        return;
    }
    int M = (L + R) / 2;
    if(x <= M) modify(x, v, L, M, st[id].l);
    else modify(x, v, M + 1, R, st[id].r);
    st[id].v = min(st[st[id].l].v, st[st[id].r].v);
}

int query(int l, int r, int L, int R, int id){
    if(l == L && r == R){
        return st[id].v;
    }
    int M = (L + R) / 2;
    if(r <= M) return query(l, r, L, M, st[id].l);
    else if(l > M) return query(l, r, M + 1, R, st[id].r);
    else{
        return min(query(l, M, L, M, st[id].l), query(M + 1, r, M + 1, R, st[id].r));
    }
}

int main(){
    StarBurstStream

    int n;
    cin >> n >> m;
    w.resize(m + 1);
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        cin >> w[i];
    }

    st.resize(2 * m);
    if(m) build(1, m);

    int q;
    cin >> q;
    while(q--){

        int t;
        cin >> t;

        if(t == 1){
            int b, r;
            cin >> b >> r;
            modify(b, r, 1, m, 0);
        }
        else{
            int s, wl;
            cin >> s >> wl;

            int ans = 1;
            if(s != n){
                int l = s, r = m;
                while(l < r){
                    int mid = (l + r + 1) / 2;
                    if(query(s, mid, 1, m, 0) >= wl) l = mid;
                    else r = mid - 1;
                }
                if(query(s, s, 1, m, 0) < wl) l = s - 1;
                ans += l - s + 1;
            }

            if(s != 1){
                int l = 1, r = s - 1;
                while(l < r){
                    int mid = (l + r) / 2;
                    if(query(mid, s - 1, 1, m, 0) >= wl) r = mid;
                    else l = mid + 1;
                }
                if(query(s - 1, s - 1, 1, m, 0) < wl) l = s;
                ans += s - l;
            }

            cout << ans << "\n";
        }

    }

    return 0;
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 696 ms 2480 KB Output is correct
2 Correct 722 ms 2680 KB Output is correct
3 Correct 698 ms 2424 KB Output is correct
4 Correct 720 ms 2428 KB Output is correct
5 Correct 692 ms 2424 KB Output is correct
6 Correct 765 ms 2808 KB Output is correct
7 Correct 771 ms 2808 KB Output is correct
8 Correct 763 ms 2680 KB Output is correct
9 Correct 39 ms 1912 KB Output is correct
10 Correct 731 ms 4344 KB Output is correct
11 Correct 703 ms 4344 KB Output is correct
12 Correct 1010 ms 5404 KB Output is correct
13 Correct 511 ms 5240 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 555 ms 1784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1422 ms 4896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 696 ms 2480 KB Output is correct
2 Correct 722 ms 2680 KB Output is correct
3 Correct 698 ms 2424 KB Output is correct
4 Correct 720 ms 2428 KB Output is correct
5 Correct 692 ms 2424 KB Output is correct
6 Correct 765 ms 2808 KB Output is correct
7 Correct 771 ms 2808 KB Output is correct
8 Correct 763 ms 2680 KB Output is correct
9 Correct 39 ms 1912 KB Output is correct
10 Correct 731 ms 4344 KB Output is correct
11 Correct 703 ms 4344 KB Output is correct
12 Correct 1010 ms 5404 KB Output is correct
13 Correct 511 ms 5240 KB Output is correct
14 Incorrect 555 ms 1784 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -