oj.uz

답안 #262496

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
262496 2020-08-13T01:52:56 Z ToMmyDong 다리 (APIO19_bridges) C++11
16 / 100
 336 ms 3704 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
#define SQ(i) ((i)*(i))
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) static_cast<int>(i.size())
#define FOR(i, j, k, in) for (int i=j; i < (k) ; i+=in)
#define RFOR(i, j, k, in) for (int i=j; i >= (k) ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i, j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(), _a.end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
template<typename T, typename S>
istream &operator >> (istream &is, pair<T, S> &p) {
    return is >> p.X >> p.Y;
}
#ifdef tmd
#define TIME(i) Timer i(#i)
#define debug(...) do {\
    fprintf(stderr, "%s - %d (%s) = ", __PRETTY_FUNCTION__, __LINE__, #__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T> void _do(T &&_x) {cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x, S &&..._t) {cerr <<_x <<" ,"; _do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s, const pair<_a, _b> &_p) {return _s << "(" << _p.X << "," << _p.Y << ")";}
template<typename It> ostream& _OUTC(ostream &_s, It _ita, It _itb)
{
    _s << "{";
    for (It _it=_ita; _it != _itb; _it++) {
        _s <<(_it == _ita?"":",")<< *_it;
    }
    _s << "}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s, const vector<_a> &_c) {return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s, const array<_a,2> &_c) {return _OUTC(_s, ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s, const array<_a,3> &_c) {return _OUTC(_s, ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s, const array<_a,4> &_c) {return _OUTC(_s, ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s, const array<_a,5> &_c) {return _OUTC(_s, ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s, const set<_a> &_c) {return _OUTC(_s, ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s, const deque<_a> &_c) {return _OUTC(_s, ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s, const map<_a,_b> &_c) {return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
class Timer {
private:
    string scope_name;
    chrono::high_resolution_clock::time_point start_time;
public:
    Timer (string name) : scope_name(name) {
        start_time = chrono::high_resolution_clock::now();
    }
    ~Timer () {
        auto stop_time = chrono::high_resolution_clock::now();
        auto length = chrono::duration_cast<chrono::microseconds>(stop_time - start_time).count();
        double mlength = double(length) * 0.001;
        debug(scope_name, mlength);
    }
};
#else
#define TIME(i)
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif

const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int iNF = 0x3f3f3f3f;
const ll MAXN = 5e4 + 5;


int zkw[MAXN*2];
int q, n, m;

void build () {
    for (int i=n-1; i>0; i--) {
        zkw[i] = min(zkw[i<<1], zkw[i<<1|1]);
    }
}

void chg (int x, int val) {
    for (zkw[x+=n]=val; x>1; x>>=1) {
        zkw[x>>1] = min(zkw[x], zkw[x^1]);
    }
}

int qry (int l, int r) {
    int ret = MOD;
    for (l+=n,r+=n; l<r; l>>=1, r>>=1) {
        if (l&1) {
            ret = min(ret, zkw[l++]);
        }
        if (r&1) {
            ret = min(ret, zkw[--r]);
        }
    }
    return ret;
}
signed main () {
    TIME(main);
    IOS();

    cin >> n >> m;
    for (int i=0; i<m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        zkw[i+n] = w;
    }
    build();

    for (cin>>q; q>0; q--) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            chg(x-1, y);
        } else {
            int ans = 1;
            x--;
            {
                int l = -1, r = x;
                while (l < r - 1) {
                    int m = (l + r) >> 1;
                    if (qry(m, x) < y) {
                        l = m;
                    } else {
                        r = m;
                    }
                }
                ans += x - r;
            }
            {
                int l = x, r = n;
                while (l < r - 1) {
                    int m = (l + r) >> 1;
                    if (qry(x, m) < y) {
                        r = m;
                    } else {
                        l = m;
                    }
                }
                ans += l - x;
            }
            cout << ans << endl;
        }
    }
    return 0;
}

Subtask #1
0 / 13.0

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

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 2552 KB Output is correct
2 Correct 153 ms 3552 KB Output is correct
3 Correct 153 ms 3704 KB Output is correct
4 Correct 149 ms 3704 KB Output is correct
5 Correct 150 ms 3576 KB Output is correct
6 Correct 219 ms 3576 KB Output is correct
7 Correct 219 ms 3640 KB Output is correct
8 Correct 209 ms 3704 KB Output is correct
9 Correct 33 ms 1912 KB Output is correct
10 Correct 182 ms 2552 KB Output is correct
11 Correct 170 ms 2556 KB Output is correct
12 Correct 336 ms 3704 KB Output is correct
13 Correct 82 ms 3448 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 1536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 2552 KB Output is correct
2 Correct 153 ms 3552 KB Output is correct
3 Correct 153 ms 3704 KB Output is correct
4 Correct 149 ms 3704 KB Output is correct
5 Correct 150 ms 3576 KB Output is correct
6 Correct 219 ms 3576 KB Output is correct
7 Correct 219 ms 3640 KB Output is correct
8 Correct 209 ms 3704 KB Output is correct
9 Correct 33 ms 1912 KB Output is correct
10 Correct 182 ms 2552 KB Output is correct
11 Correct 170 ms 2556 KB Output is correct
12 Correct 336 ms 3704 KB Output is correct
13 Correct 82 ms 3448 KB Output is correct
14 Incorrect 137 ms 2424 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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