oj.uz

Submission #522406

# Submission time Handle Problem Language Result Execution time Memory
522406 2022-02-04T22:17:56 Z BalintR Street Lamps (APIO19_street_lamps) C++17
60 / 100
 5000 ms 21176 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2594 ms 14136 KB Output is correct
2 Correct 2551 ms 14784 KB Output is correct
3 Correct 2663 ms 15716 KB Output is correct
4 Correct 2666 ms 18972 KB Output is correct
5 Correct 3926 ms 21176 KB Output is correct
6 Execution timed out 5009 ms 18456 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 209 ms 19428 KB Output is correct
6 Correct 2333 ms 20696 KB Output is correct
7 Correct 3735 ms 20504 KB Output is correct
8 Correct 28 ms 17032 KB Output is correct
9 Correct 15 ms 12392 KB Output is correct
10 Correct 16 ms 12280 KB Output is correct
11 Correct 15 ms 11904 KB Output is correct
12 Correct 65 ms 16856 KB Output is correct
13 Correct 29 ms 17132 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 254 ms 17240 KB Output is correct
6 Correct 4542 ms 17660 KB Output is correct
7 Correct 4757 ms 17980 KB Output is correct
8 Correct 304 ms 18592 KB Output is correct
9 Correct 4160 ms 14564 KB Output is correct
10 Correct 381 ms 14412 KB Output is correct
11 Correct 4191 ms 14572 KB Output is correct
12 Correct 384 ms 14420 KB Output is correct
13 Correct 4165 ms 14564 KB Output is correct
14 Correct 361 ms 14416 KB Output is correct
15 Correct 65 ms 16792 KB Output is correct
16 Correct 38 ms 17088 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2594 ms 14136 KB Output is correct
9 Correct 2551 ms 14784 KB Output is correct
10 Correct 2663 ms 15716 KB Output is correct
11 Correct 2666 ms 18972 KB Output is correct
12 Correct 3926 ms 21176 KB Output is correct
13 Execution timed out 5009 ms 18456 KB Time limit exceeded
14 Halted 0 ms 0 KB -