Submission #522406

#	Time	Username	Problem	Language	Result	Execution time	Memory
522406		BalintR	Street Lamps (APIO19_street_lamps)	C++17	60 / 100	5009 ms	21176 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize "Ofast"

#define pb push_back
inline constexpr int lg2(int x){return 32 - __builtin_clz(x);}

const int MDIGITS = 7, PW10[MDIGITS] = {0, 10, 100, 1000, 10000, 100000, 1000000};
const int IO_SZ = 6 << 20;
char _buf[IO_SZ], *_ii = _buf, *_oi = _buf;
template <typename T> inline void scan(T &x){for(x=*_ii++-'0'; *_ii++>='0'; x=x*10+_ii[-1]-'0');}
template <typename T> inline void print(T x){int dg=0; while(dg<MDIGITS && PW10[dg]<=x) dg++; for(char *i=_oi+dg-1; i>=_oi; --i, x/=10) *i=x%10+'0'; _oi+=dg;}

// type 1 - increase [l, n-r) by v
// type 2 - query [l, n-r), v is extra
struct Event {
    int type, l, r, v;
};
vector<Event> events;

const int MN = 3e5 + 5;
int n, q;
char *arr;
int bit1[MN];
int lvl[MN];

int xArr[MN*2], yArr[MN*2], vArr[MN*2], ai;

int bit1Lb(int x){
    if(x <= 0) return -1;
    int i = 0;
    for(int pw = 1 << lg2(n); pw > 0; pw >>= 1) if(i + pw <= n && bit1[i + pw] < x) x -= bit1[i += pw];
    return i;
}

int main(){
    fread(_buf, 1, IO_SZ, stdin);
    scan(n); scan(q);
    arr = _ii; _ii += n+1;
    for(int i = 0; i < n; ++i) if(!(arr[i] -= '0')) for(int j = i+1; j <= n; j += j & -j) bit1[j]++;

    events.reserve(n*2);
    for (int i = 1; i <= q; ++i) {
        bool type = *_ii == 't';
        _ii += type ? 7 : 6;

        if(type){
            int a; scan(a); a--;
            int cur = 0;
            for(int j = a+1; j; j -= j & -j) cur += bit1[j];
            int l = bit1Lb(cur - !arr[a]) + 1;
            int r = bit1Lb(cur+1);

            if(arr[a]){
                int prv = lvl[r];
                events.pb({1, l, n-r, i-prv});

                arr[a] = 0;
                lvl[a] = lvl[r] = i;
                for(int j = a+1; j <= n; j += j & -j) bit1[j]++;
            }
            else {
                if(l < a){
                    int prv = lvl[a];
                    events.pb({1, l, n-a, i-prv});
                }
                if(r > a+1){
                    int prv = lvl[r];
                    events.pb({1, a+1, n-r, i-prv});
                }

                arr[a] = 1;
                lvl[r] = i;
                for(int j = a+1; j <= n; j += j & -j) bit1[j]--;
            }
        }
        else {
            int l, r;
            scan(l); scan(r);
            l--; r--;
            int qRes = 0;
            for(int j = l+1; j; j -= j & -j) qRes += bit1[j];
            int mr = bit1Lb(qRes - !arr[l] + 1);
            events.pb({2, l, n-r, mr >= r ? i-lvl[mr] : 0});
        }
    }

    for(Event event : events){
        if(event.type == 1){
            xArr[ai] = event.l;
            yArr[ai] = event.r;
            vArr[ai] = event.v;
            ai++;
        }
        else {
            int x = event.l, y = event.r, res = event.v;
            for (int i = 0; i < ai; i++) {
                if(xArr[i] <= x && yArr[i] <= y) res += vArr[i];
            }
            print(res); *_oi++ = '\n';
        }
    }
    fwrite(_buf, 1, _oi-_buf, stdout);
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:37:10: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     fread(_buf, 1, IO_SZ, stdin);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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