제출 #1196916

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196916		zaki98	가로등 (APIO19_street_lamps)	C++20	20 / 100	149 ms	16944 KiB

street_lamps

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef long long ll;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(c) (c).begin(), (c).end()
#define pii pair<int,int>
#define pll pair<long long, long long>
#define sz(a) (int)a.size()
// permutation of the last layer
#define LOO(i,a,b) for (int i = a; i <= b; i++)
#define OOL(i,a,b) for (int i = b; i >= a; i--)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)
using namespace std;
typedef tree<int,null_type, less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
typedef tree<int,null_type, less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
constexpr ll MAX = 998244353;
void iO() {
    freopen("haircut.out", "w",stdout);
    freopen("haircut.in", "r",stdin);
}
vector<int> make_sorted_index(vector<int> const &values) {
    vector<int> index(values.size());
    iota(index.begin(), index.end(), 0);
    stable_sort(index.begin(), index.end(), [&values](int a, int b) {
        return values[a] < values[b];
    });
    return index;
} // this function is so skibidi
struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }

    int operator()(pii x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(FIXED_RANDOM * x.first + x.second + FIXED_RANDOM);
    }
}; // gp_hash_table custom hash so skibid
class seggy {
public:
    int sz;
    seggy(vector<int> const &array, function<ll(ll, ll)> const &th) {
        sz = array.size();
        seg.resize(4*array.size());
        f = th;
        build(1, 0, sz-1, array);
    }
    ll answ(int l, int r) {
        return queryans(1, l, r, 0, sz-1);
    }
    void upd(int pos, int val) {
        updans(1, 0, sz-1, pos, val);
    }
private:
    vector<ll> seg;
    function<ll(ll, ll)> f;
    void build(int v, int l, int r, vector<int> const &array) {
        if (l==r) {
            seg[v] = array[l];
            return;
        }
        int mid = (l+r)/2;
        build(2*v, l ,mid, array);
        build(2*v+1, mid+1, r, array);
        seg[v] = f(seg[2*v], seg[2*v+1]);
    }
    ll queryans(int v, int l, int r, int tl, int tr) {
        if (l==tl&&r==tr) return seg[v];
        int mid = (tl+tr)/2;
        int ans;
        bool setans = false;
        if (r > mid) {
            ans = queryans(2*v+1, max(mid+1,l), r, mid+1, tr);
            setans = true;
        }
        if (l <= mid) {
            if (setans) {
                ans = f(ans, queryans(2*v, l, min(r, mid), tl, mid));
            }
            else {
                ans = queryans(2*v, l, min(r, mid), tl, mid);
            }
        }
        return ans;
    }
    void updans(int v, int l, int r, int pos, int val) {
        if (l==r) {
            seg[v] = val;
            return;
        }
        int mid = (l+r)/2;
        if (mid >= pos) {
            updans(2*v, l, mid, pos, val);
        }
        else {
            updans(2*v+1, mid+1, r, pos, val);
        }
        seg[v] = f(seg[2*v], seg[2*v+1]);
    }
};
ll oper(ll a, ll b) {return max(a, b);}
int solve() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<int> times(n, 1e9);
    LOO(i, 0, n-1) if (s[i]=='1') times[i] = -1;
    vector<pair<int, pii>> queries;
    LOO(i, 0, q-1) {
        string s1;
        cin >> s1;
        if (s1=="query") {
            int a, b;
            cin >> a >> b;
            a--;b--;
            queries.PB(MP(i, MP(a,b)));
        }
        else {
            int k;
            cin >> k;
            k--;
            times[k] = i;
        }
    }
    seggy cool = seggy(times, oper);
    for (auto ele: queries) {
        cout << max(ele.F - cool.answ(ele.S.F, ele.S.S-1), 0LL) << "\n";
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 //   iO();
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
        //cout << flush;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp: In function 'void iO()':
street_lamps.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     freopen("haircut.out", "w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen("haircut.in", "r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20