oj.uz

Submission #538441

# Submission time Handle Problem Language Result Execution time Memory
538441 2022-03-17T00:19:30 Z Evang Street Lamps (APIO19_street_lamps) C++17
100 / 100
 933 ms 71532 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


using vup = vc<array<int, 3>>;
const int N = 3e5+5;
const int Q = N;
int n, q, ans[Q];
bitset<Q> t;

template<typename T>
struct BIT {
    T bit[N]{};
    vc<pair<int, T>> un;

    void _upd(int i, T x){
        while(i<=n+2){
            bit[i] += x;
            i += i&-i;
        }
    }
    void upd(int i, T x){
        un.eb(i, x);
        _upd(i, x);
    }
    T sum(int r){
        T s = 0;
        while(r>0){
            s += bit[r];
            r -= r&-r;
        }
        return s;
    }
    T qry(int l, int r){
        return sum(r) - sum(l-1);
    }
    void clear(){
        while(!un.empty()){
            auto[i, x] = un.back();
            un.pop_back();
            _upd(i, -x);
        }
    }
};

BIT<int> bit, a;

void cdq(vup &e, int l, int r){
    if(l==r)
        return;
    int m = (l+r)/2;
    cdq(e, l, m);
    cdq(e, m+1, r);

    bit.clear();
    int j = l;
    for(int i = m+1; i <= r; ++i){
        if(t[abs(e[i][0])]==0)
            continue;

        while(j<=m && (t[abs(e[j][0])]==1 || e[j][1] <= e[i][1])){
            if(t[abs(e[j][0])]==0)
                bit.upd(e[j][2], e[j][0]);
            ++j;
        }
        ans[e[i][0]] += bit.qry(1, e[i][2]);
    }

    vup res;
    j = l;
    int i = m+1;
    while(j<=m || i <= r){
        if(j>m||i<=r&&e[i][1]<e[j][1])
            res.pb(e[i++]);
        else
            res.pb(e[j++]);
    }
    for(i = l; i <= r; ++i)
        e[i] = res[i-l];
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> n >> q;
    for(int i = 1; i <= n; ++i){
        char c;
        cin >> c;
        if(c=='1')
            a.upd(i, 1);
    }

    vup e;
    for(int i = 1; i <= q; ++i){
        str o;
        cin >> o;
        if(o=="toggle"){
            int j;
            cin >> j;
            int l = j, r = j;
            for(int u = n; u > 0; u /= 2){
                while(l-u>0&&a.qry(l-u, j-1)==j-(l-u))
                    l -= u;
                while(r+u<=n&&a.qry(j+1, r+u)==r+u-j)
                    r += u;
            }

            if(a.qry(j, j)==1){
                e.pb(array<int, 3>{i, j+1, r+1});
                e.pb(array<int, 3>{i, l, j});
                e.pb(array<int, 3>{-i, j+1, j});
                e.pb(array<int, 3>{-i, l, r+1});
                a.upd(j, -1);
            }else{
                e.pb(array<int, 3>{-i, j+1, r+1});
                e.pb(array<int, 3>{-i, l, j});
                e.pb(array<int, 3>{i, j+1, j});
                e.pb(array<int, 3>{i, l, r+1});
                a.upd(j, 1);
            }
        }else{
            t[i] = 1;
            int l, r;
            cin >> l >> r;
            --r;
            e.pb(array<int, 3>{i, l, r});
            if(a.qry(l, r)==r-l+1)
                ans[i] = i;
        }
    }

    cdq(e, 0, ssize(e)-1);

    for(int i = 1; i <= q; ++i)
        if(t[i])
            cout << ans[i] << el;
}

Compilation message

street_lamps.cpp: In function 'void cdq(vup&, int, int)':
street_lamps.cpp:130:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  130 |         if(j>m||i<=r&&e[i][1]<e[j][1])

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2688 KB Output is correct
3 Correct 2 ms 2684 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2684 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 40100 KB Output is correct
2 Correct 514 ms 41540 KB Output is correct
3 Correct 596 ms 41564 KB Output is correct
4 Correct 729 ms 41820 KB Output is correct
5 Correct 657 ms 37204 KB Output is correct
6 Correct 545 ms 43332 KB Output is correct
7 Correct 263 ms 17088 KB Output is correct
8 Correct 280 ms 19460 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 4 ms 2820 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 933 ms 71532 KB Output is correct
6 Correct 833 ms 45588 KB Output is correct
7 Correct 668 ms 36632 KB Output is correct
8 Correct 273 ms 19176 KB Output is correct
9 Correct 130 ms 11184 KB Output is correct
10 Correct 153 ms 16116 KB Output is correct
11 Correct 150 ms 16224 KB Output is correct
12 Correct 254 ms 16668 KB Output is correct
13 Correct 265 ms 18972 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 4 ms 2772 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 275 ms 18508 KB Output is correct
6 Correct 414 ms 36800 KB Output is correct
7 Correct 538 ms 43348 KB Output is correct
8 Correct 748 ms 69480 KB Output is correct
9 Correct 440 ms 45152 KB Output is correct
10 Correct 463 ms 68152 KB Output is correct
11 Correct 417 ms 46168 KB Output is correct
12 Correct 463 ms 68128 KB Output is correct
13 Correct 405 ms 45220 KB Output is correct
14 Correct 452 ms 70188 KB Output is correct
15 Correct 264 ms 17012 KB Output is correct
16 Correct 272 ms 19548 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2688 KB Output is correct
3 Correct 2 ms 2684 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2684 KB Output is correct
8 Correct 479 ms 40100 KB Output is correct
9 Correct 514 ms 41540 KB Output is correct
10 Correct 596 ms 41564 KB Output is correct
11 Correct 729 ms 41820 KB Output is correct
12 Correct 657 ms 37204 KB Output is correct
13 Correct 545 ms 43332 KB Output is correct
14 Correct 263 ms 17088 KB Output is correct
15 Correct 280 ms 19460 KB Output is correct
16 Correct 3 ms 2816 KB Output is correct
17 Correct 4 ms 2820 KB Output is correct
18 Correct 3 ms 2772 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 933 ms 71532 KB Output is correct
21 Correct 833 ms 45588 KB Output is correct
22 Correct 668 ms 36632 KB Output is correct
23 Correct 273 ms 19176 KB Output is correct
24 Correct 130 ms 11184 KB Output is correct
25 Correct 153 ms 16116 KB Output is correct
26 Correct 150 ms 16224 KB Output is correct
27 Correct 254 ms 16668 KB Output is correct
28 Correct 265 ms 18972 KB Output is correct
29 Correct 2 ms 2644 KB Output is correct
30 Correct 2 ms 2772 KB Output is correct
31 Correct 4 ms 2772 KB Output is correct
32 Correct 3 ms 2772 KB Output is correct
33 Correct 275 ms 18508 KB Output is correct
34 Correct 414 ms 36800 KB Output is correct
35 Correct 538 ms 43348 KB Output is correct
36 Correct 748 ms 69480 KB Output is correct
37 Correct 440 ms 45152 KB Output is correct
38 Correct 463 ms 68152 KB Output is correct
39 Correct 417 ms 46168 KB Output is correct
40 Correct 463 ms 68128 KB Output is correct
41 Correct 405 ms 45220 KB Output is correct
42 Correct 452 ms 70188 KB Output is correct
43 Correct 264 ms 17012 KB Output is correct
44 Correct 272 ms 19548 KB Output is correct
45 Correct 259 ms 25704 KB Output is correct
46 Correct 299 ms 25160 KB Output is correct
47 Correct 442 ms 25528 KB Output is correct
48 Correct 715 ms 41756 KB Output is correct
49 Correct 177 ms 17048 KB Output is correct
50 Correct 166 ms 17080 KB Output is correct
51 Correct 180 ms 17312 KB Output is correct
52 Correct 176 ms 17096 KB Output is correct
53 Correct 179 ms 17076 KB Output is correct
54 Correct 175 ms 17044 KB Output is correct