oj.uz

Submission #538440

# Submission time Handle Problem Language Result Execution time Memory
538440 2022-03-17T00:05:34 Z Evang Street Lamps (APIO19_street_lamps) C++17
100 / 100
 924 ms 81604 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;
bitset<Q> t;
ll ans[Q];

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){
        ++i;
        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){
        ++r; ++l;
        return sum(r) - sum(l-1);
    }
    void clear(){
        while(!un.empty()){
            auto[i, x] = un.back();
            un.pop_back();
            _upd(i, -x);
        }
    }
};

BIT<ll> bit;
BIT<int> 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:134:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  134 |         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 3796 KB Output is correct
2 Correct 2 ms 3852 KB Output is correct
3 Correct 2 ms 3860 KB Output is correct
4 Correct 2 ms 3860 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 2 ms 3860 KB Output is correct
7 Correct 2 ms 3860 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 47380 KB Output is correct
2 Correct 525 ms 50324 KB Output is correct
3 Correct 597 ms 51852 KB Output is correct
4 Correct 743 ms 53084 KB Output is correct
5 Correct 690 ms 46764 KB Output is correct
6 Correct 569 ms 54384 KB Output is correct
7 Correct 268 ms 24920 KB Output is correct
8 Correct 282 ms 27276 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3924 KB Output is correct
2 Correct 4 ms 4052 KB Output is correct
3 Correct 3 ms 3924 KB Output is correct
4 Correct 3 ms 3924 KB Output is correct
5 Correct 924 ms 80976 KB Output is correct
6 Correct 848 ms 53764 KB Output is correct
7 Correct 656 ms 42004 KB Output is correct
8 Correct 278 ms 22628 KB Output is correct
9 Correct 138 ms 14524 KB Output is correct
10 Correct 151 ms 19692 KB Output is correct
11 Correct 155 ms 19592 KB Output is correct
12 Correct 264 ms 20276 KB Output is correct
13 Correct 272 ms 22708 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 2 ms 3924 KB Output is correct
3 Correct 3 ms 4052 KB Output is correct
4 Correct 3 ms 4052 KB Output is correct
5 Correct 287 ms 27172 KB Output is correct
6 Correct 465 ms 42412 KB Output is correct
7 Correct 571 ms 54384 KB Output is correct
8 Correct 759 ms 81604 KB Output is correct
9 Correct 425 ms 54716 KB Output is correct
10 Correct 479 ms 78696 KB Output is correct
11 Correct 421 ms 54656 KB Output is correct
12 Correct 469 ms 78812 KB Output is correct
13 Correct 425 ms 54628 KB Output is correct
14 Correct 481 ms 78908 KB Output is correct
15 Correct 275 ms 24852 KB Output is correct
16 Correct 282 ms 27252 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3852 KB Output is correct
3 Correct 2 ms 3860 KB Output is correct
4 Correct 2 ms 3860 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 2 ms 3860 KB Output is correct
7 Correct 2 ms 3860 KB Output is correct
8 Correct 484 ms 47380 KB Output is correct
9 Correct 525 ms 50324 KB Output is correct
10 Correct 597 ms 51852 KB Output is correct
11 Correct 743 ms 53084 KB Output is correct
12 Correct 690 ms 46764 KB Output is correct
13 Correct 569 ms 54384 KB Output is correct
14 Correct 268 ms 24920 KB Output is correct
15 Correct 282 ms 27276 KB Output is correct
16 Correct 3 ms 3924 KB Output is correct
17 Correct 4 ms 4052 KB Output is correct
18 Correct 3 ms 3924 KB Output is correct
19 Correct 3 ms 3924 KB Output is correct
20 Correct 924 ms 80976 KB Output is correct
21 Correct 848 ms 53764 KB Output is correct
22 Correct 656 ms 42004 KB Output is correct
23 Correct 278 ms 22628 KB Output is correct
24 Correct 138 ms 14524 KB Output is correct
25 Correct 151 ms 19692 KB Output is correct
26 Correct 155 ms 19592 KB Output is correct
27 Correct 264 ms 20276 KB Output is correct
28 Correct 272 ms 22708 KB Output is correct
29 Correct 2 ms 3924 KB Output is correct
30 Correct 2 ms 3924 KB Output is correct
31 Correct 3 ms 4052 KB Output is correct
32 Correct 3 ms 4052 KB Output is correct
33 Correct 287 ms 27172 KB Output is correct
34 Correct 465 ms 42412 KB Output is correct
35 Correct 571 ms 54384 KB Output is correct
36 Correct 759 ms 81604 KB Output is correct
37 Correct 425 ms 54716 KB Output is correct
38 Correct 479 ms 78696 KB Output is correct
39 Correct 421 ms 54656 KB Output is correct
40 Correct 469 ms 78812 KB Output is correct
41 Correct 425 ms 54628 KB Output is correct
42 Correct 481 ms 78908 KB Output is correct
43 Correct 275 ms 24852 KB Output is correct
44 Correct 282 ms 27252 KB Output is correct
45 Correct 272 ms 31552 KB Output is correct
46 Correct 299 ms 31396 KB Output is correct
47 Correct 434 ms 32932 KB Output is correct
48 Correct 724 ms 53088 KB Output is correct
49 Correct 177 ms 22480 KB Output is correct
50 Correct 176 ms 22448 KB Output is correct
51 Correct 180 ms 22624 KB Output is correct
52 Correct 186 ms 22884 KB Output is correct
53 Correct 184 ms 22928 KB Output is correct
54 Correct 177 ms 22896 KB Output is correct