oj.uz

Submission #982618

# Submission time Handle Problem Language Result Execution time Memory
982618 2024-05-14T13:53:53 Z Tuanlinh123 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 3302 ms 355424 KB 
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=300005;
vector <ll> upd[maxn];
vector <pll> Q[maxn];
ll n, q, a[maxn], answer[maxn];
vector <pair<pll, pll>> U[maxn];
ll cnt[maxn/100][maxn/100];

namespace intervals
{
    set <pair<pll, ll>> s;
    void init() {s.insert({{1, q}, 1}), U[1].pb({{1, q}, {1, 1}});}

    void add(ll l, ll r, ll t)
    {
        vector <pair<pll, ll>> sn;
        auto ptr=s.lower_bound(mp(mp(l, 0), 0));
        if (ptr!=s.begin()) ptr--;
        while (ptr!=s.end() && (*ptr).fi.fi<=r)
            sn.pb(*ptr), ptr=s.erase(ptr);
        s.insert({{l, r}, t+1}), U[t].pb({{l, r}, {t+1, 1}});
        for (ll i=0; i<sz(sn); i++)
        {
            ll L=sn[i].fi.fi, R=sn[i].fi.se, V=sn[i].se;
            if (R<l || L>r) s.insert({{L, R}, V});
            else if (l<=L && R<=r) U[t].pb({{L, R}, {V, -1}});
            else if (L<l && r<R) U[t].pb({{l, r}, {V, -1}}), s.insert({{L, l-1}, V}), s.insert({{r+1, R}, V});
            else if (L<l) U[t].pb({{l, R}, {V, -1}}), s.insert({{L, l-1}, V});
            else U[t].pb({{L, r}, {V, -1}}), s.insert({{r+1, R}, V});
        }
    }
} 

struct BIT2D_RURQ
{
    ll n;
    vector <vector <ll>> pos, A, B, C, D; // a[x][y], a[x][y]*x, a[x][y]*y, a[x][y]*x*y
    BIT2D_RURQ (ll n): n(n) {pos=A=B=C=D=vector <vector <ll>> (n+1);}

    void fupdate(ll x, ll y) {for (; x<=n; x+=x&(-x)) pos[x].pb(y);}
    void fupdate(ll x, ll y, ll l, ll r){fupdate(x, l), fupdate(x, r+1), fupdate(y+1, l), fupdate(y+1, r+1);}

    void build()
    {
        for (ll i=1; i<=n; i++)
        {
            pos[i].pb(0), sort(pos[i].begin(), pos[i].end());
            pos[i].resize(unique(pos[i].begin(), pos[i].end())-pos[i].begin());
            A[i]=B[i]=C[i]=D[i]=vector <ll> (sz(pos[i]), 0);
        }
    }

    void update(ll x, ll y, ll val)
    {
        for (ll i=x; i<=n; i+=i&(-i))
            for (ll j=lower_bound(pos[i].begin(), pos[i].end(), y)-pos[i].begin(); j<sz(pos[i]); j+=j&(-j))
                A[i][j]+=val, B[i][j]+=val*x, C[i][j]+=val*y, D[i][j]+=val*x*y;
    }
    void update(ll x, ll y, ll l, ll r, ll val) {update(x, l, val), update(x, r+1, -val), update(y+1, l, -val), update(y+1, r+1, val);}

    ll query(ll x, ll y)
    {
        ll a=0, b=0, c=0, d=0;
        for (ll i=x; i; i-=i&(-i))
            for (ll j=upper_bound(pos[i].begin(), pos[i].end(), y)-pos[i].begin()-1; j; j-=j&(-j))
                a+=A[i][j], b+=B[i][j], c+=C[i][j], d+=D[i][j];
        return a*(x+1)*(y+1)-b*(y+1)-c*(x+1)+d;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (ll i=1; i<=n; i++) {char c; cin >> c; a[i]=c=='1';}
    for (ll i=1; i<=q; i++) answer[i]=-1;
    for (ll i=1; i<=q; i++)
    {
        string t; cin >> t;
        if (t=="query") {ll l, r; cin >> l >> r, Q[r-1].pb({l, i}), answer[i]=0;}
        else {ll x; cin >> x, upd[x].pb(i);}
    }
    intervals::init();
    for (ll i=1; i<=n; i++)
    {
        upd[i].pb(q);
        for (ll j=0, s=a[i]; j<sz(upd[i]); j++, s^=1)
            if (!s) intervals::add(j?upd[i][j-1]+1:1, upd[i][j], i);
    }
    BIT2D_RURQ S(n);
    for (ll i=1; i<=n; i++)
        for (ll j=0; j<sz(U[i]); j++)
            S.fupdate(U[i][j].se.fi, U[i][j].se.fi, U[i][j].fi.fi, U[i][j].fi.se);
    S.build();
    for (ll i=1; i<=n; i++)
    {
        for (ll j=0; j<sz(U[i]); j++)
            S.update(U[i][j].se.fi, U[i][j].se.fi, U[i][j].fi.fi, U[i][j].fi.se, U[i][j].se.se);
        for (auto [l, id]:Q[i]) answer[id]=S.query(l, id);
    }
    for (ll i=1; i<=q; i++)
        if (answer[i]>=0) cout << answer[i] << " ";
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23896 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Correct 6 ms 23896 KB Output is correct
4 Correct 6 ms 24156 KB Output is correct
5 Correct 6 ms 23988 KB Output is correct
6 Correct 6 ms 24156 KB Output is correct
7 Correct 6 ms 23900 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 67224 KB Output is correct
2 Correct 814 ms 77072 KB Output is correct
3 Correct 1096 ms 97816 KB Output is correct
4 Correct 2281 ms 272664 KB Output is correct
5 Correct 1585 ms 221772 KB Output is correct
6 Correct 2327 ms 296956 KB Output is correct
7 Correct 1064 ms 274500 KB Output is correct
8 Correct 261 ms 129872 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24664 KB Output is correct
2 Correct 9 ms 24664 KB Output is correct
3 Correct 8 ms 24412 KB Output is correct
4 Correct 6 ms 24412 KB Output is correct
5 Correct 3302 ms 345656 KB Output is correct
6 Correct 2603 ms 291688 KB Output is correct
7 Correct 1816 ms 220884 KB Output is correct
8 Correct 330 ms 129420 KB Output is correct
9 Correct 68 ms 30256 KB Output is correct
10 Correct 77 ms 30800 KB Output is correct
11 Correct 75 ms 30756 KB Output is correct
12 Correct 1292 ms 275376 KB Output is correct
13 Correct 306 ms 129472 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 24412 KB Output is correct
2 Correct 8 ms 24668 KB Output is correct
3 Correct 11 ms 24820 KB Output is correct
4 Correct 10 ms 24748 KB Output is correct
5 Correct 947 ms 192616 KB Output is correct
6 Correct 1776 ms 236676 KB Output is correct
7 Correct 2484 ms 295872 KB Output is correct
8 Correct 3268 ms 355424 KB Output is correct
9 Correct 1054 ms 109436 KB Output is correct
10 Correct 1119 ms 108184 KB Output is correct
11 Correct 1069 ms 106232 KB Output is correct
12 Correct 1123 ms 106248 KB Output is correct
13 Correct 1073 ms 106816 KB Output is correct
14 Correct 1100 ms 106704 KB Output is correct
15 Correct 1218 ms 275352 KB Output is correct
16 Correct 302 ms 129464 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23896 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Correct 6 ms 23896 KB Output is correct
4 Correct 6 ms 24156 KB Output is correct
5 Correct 6 ms 23988 KB Output is correct
6 Correct 6 ms 24156 KB Output is correct
7 Correct 6 ms 23900 KB Output is correct
8 Correct 635 ms 67224 KB Output is correct
9 Correct 814 ms 77072 KB Output is correct
10 Correct 1096 ms 97816 KB Output is correct
11 Correct 2281 ms 272664 KB Output is correct
12 Correct 1585 ms 221772 KB Output is correct
13 Correct 2327 ms 296956 KB Output is correct
14 Correct 1064 ms 274500 KB Output is correct
15 Correct 261 ms 129872 KB Output is correct
16 Correct 9 ms 24664 KB Output is correct
17 Correct 9 ms 24664 KB Output is correct
18 Correct 8 ms 24412 KB Output is correct
19 Correct 6 ms 24412 KB Output is correct
20 Correct 3302 ms 345656 KB Output is correct
21 Correct 2603 ms 291688 KB Output is correct
22 Correct 1816 ms 220884 KB Output is correct
23 Correct 330 ms 129420 KB Output is correct
24 Correct 68 ms 30256 KB Output is correct
25 Correct 77 ms 30800 KB Output is correct
26 Correct 75 ms 30756 KB Output is correct
27 Correct 1292 ms 275376 KB Output is correct
28 Correct 306 ms 129472 KB Output is correct
29 Correct 7 ms 24412 KB Output is correct
30 Correct 8 ms 24668 KB Output is correct
31 Correct 11 ms 24820 KB Output is correct
32 Correct 10 ms 24748 KB Output is correct
33 Correct 947 ms 192616 KB Output is correct
34 Correct 1776 ms 236676 KB Output is correct
35 Correct 2484 ms 295872 KB Output is correct
36 Correct 3268 ms 355424 KB Output is correct
37 Correct 1054 ms 109436 KB Output is correct
38 Correct 1119 ms 108184 KB Output is correct
39 Correct 1069 ms 106232 KB Output is correct
40 Correct 1123 ms 106248 KB Output is correct
41 Correct 1073 ms 106816 KB Output is correct
42 Correct 1100 ms 106704 KB Output is correct
43 Correct 1218 ms 275352 KB Output is correct
44 Correct 302 ms 129464 KB Output is correct
45 Correct 267 ms 46416 KB Output is correct
46 Correct 415 ms 53392 KB Output is correct
47 Correct 1140 ms 131612 KB Output is correct
48 Correct 2313 ms 272812 KB Output is correct
49 Correct 88 ms 31448 KB Output is correct
50 Correct 79 ms 31308 KB Output is correct
51 Correct 88 ms 31280 KB Output is correct
52 Correct 77 ms 32012 KB Output is correct
53 Correct 82 ms 31828 KB Output is correct
54 Correct 80 ms 31936 KB Output is correct