Submission #1105320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105320		monaxia	Hotspot (NOI17_hotspot)	C++17	0 / 100	9 ms	63056 KiB

hotspot

#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define mod (long long)(1e9 + 7)
#define eps (long long)(1e-9)
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
ll LIMIT = 2e3 + 5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random (ll l, ll r){return uniform_int_distribution <ll> (l, r)(rng);}


vector <ll> st(8e6 + 5, 0);

void update(ll idx, ll l, ll r, ll i, ll val){
    if(i < l || r < i) return;

    if(l == r){
        st[idx] = val;
        return;
    }

    ll mid = (l + r) >> 1;

    update(idx * 2, l, mid, i, val);
    update(idx * 2 + 1, mid + 1, r, i, val);

    st[idx] = st[idx * 2] + st[idx * 2 + 1];
}

ll sum(ll idx, ll l, ll r, ll u, ll v){
    if(r < l) return 0;

    if(r < u || v < l) return 0;
    if(u <= l && r <= v) return st[idx];

    ll mid = (l + r) >> 1;

    return sum(idx * 2, l, mid, u, v) + sum(idx * 2 + 1, mid + 1, r, u, v);
}

void solve(){
    ll n, q;
    cin >> n >> q;

    for(ll i = 1; i <= n; i ++){
        int x; cin >> x;
        update(1, 1, n, i, x);
    }


    for(ll _ = 1; _ <= q; _ ++){
        // for(int i = 1; i <= n; i ++) cout << sum(1, 1, n, i, i) << " "; cout << "\n";
        ll type, l, r;
        cin >> type >> l >> r;

        if(type == 1){
            update(1, 1, n, l, r);
            continue;
        }

        if(type == 2){
            if(l == r){
                 cout << sum(1, 1, n, l, l) << "\n";
                 continue;
            }

            ll idx = 1, bonus = 0, mid = (1 + n) >> 1, u = 1, v = n, target = sum(1, 1, n, l, r) / 2.0;  
            while(l > mid || r <= mid){
                mid = (u + v) >> 1;

                if(l > mid){
                    u = mid + 1;
                    idx = idx * 2 + 1;
                    continue;
                }

                if(r <= mid){
                    v = mid;
                    idx = idx * 2;
                    continue;
                }
            }

            if(l > 1) bonus = - sum(1, 1, n, u, l - 1);

            while(u < v){
                mid = (u + v) >> 1;

                if(st[idx * 2] + bonus >= target) {
                    idx = idx * 2;
                    v = mid;
                }

                else{
                    bonus += st[idx * 2];
                    idx = idx * 2 + 1;
                    u = mid + 1;
                    
                }

            }

            // cout << u << " " << target << "\n";
            ll ans = abs(sum(1, 1, n, l, u - 1) - sum(1, 1, n, u, r));
            if(u > 2) ans = min(ans, abs(sum(1, 1, n, l, u - 2) - sum(1, 1, n, u - 1, r)));
            if(u < r) ans = min(ans, abs(sum(1, 1, n, l, u) - sum(1, 1, n, u + 1, r)));
            cout << ans << "\n";
        }
    }
}


signed main()
{
    // cin.tie(0)->sync_with_stdio(0);
 
    if(fopen("TOY.inp", "r")){
        freopen("TOY.inp", "r", stdin);
        freopen("TOY.out", "w", stdout);
    }
    
    // cout << 1; return 0;

    ll n = 1;

    // cin >> n;

    while(n) {
        solve();
        n --;
        // cout << "\n";
    }
 
    // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Compilation message (stderr)

hotspot.cpp: In function 'int main()':
hotspot.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen("TOY.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen("TOY.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 18
• Subtask 5: 0 / 26
• Subtask 6: 0 / 36