oj.uz

Submission #1073684

# Submission time Handle Problem Language Result Execution time Memory
1073684 2024-08-24T17:58:27 Z andrei_iorgulescu Street Lamps (APIO19_street_lamps) C++14
100 / 100
 1780 ms 101280 KB 
#include <bits/stdc++.h>

using namespace std;

int n, q;
char a[300005], a_ret[300005];

vector<int> ps[300005], aib[300005];
vector<pair<int,int>> vv;

struct event
{
    int tip, x, y;///doar x daca e tip 1 (upd), altfel tip 2 (query)
};

event v[300005];

void build_aib2d_stuff()
{
    sort(vv.begin(), vv.end(), [](pair<int,int> A, pair<int,int> B)
    {
        return A.second < B.second;
    });
    for (int i = 1; i <= n; i++)
        ps[i].push_back(0);
    for (auto it : vv)
    {
        for (int i = it.first; i <= n; i += (i & -i))
            if (ps[i].back() != it.second)
                ps[i].push_back(it.second);
        for (int i = it.first; i > 0; i -= (i & -i))
            if (ps[i].back() != it.second)
                ps[i].push_back(it.second);
    }
    for (int i = 1; i <= n; i++)
        aib[i].resize(ps[i].size());
}

int get_pos(int unde, int y)
{
    int st = 0, pas = 1 << 19;
    while (pas != 0)
    {
        if (st + pas < ps[unde].size() and ps[unde][st + pas] <= y)
            st += pas;
        pas /= 2;
    }
    if (ps[unde][st] != y)
        assert(false);
    return st;
}

void update(int x, int y, int val)
{
    for (int i = x; i <= n; i += (i & -i))
    {
        for (int j = get_pos(i,y); j < ps[i].size(); j += (j & -j))
            aib[i][j] += val;
    }
}

int query(int x, int y)
{
    int rr = 0;
    for (int i = x; i > 0; i -= (i & -i))
    {
        for (int j = get_pos(i, y); j > 0; j -= (j & -j))
            rr += aib[i][j];
    }
    return rr;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i], a_ret[i] = a[i];
    for (int i = 1; i <= q; i++)
    {
        string type;
        cin >> type;
        if (type == "toggle")
        {
            v[i].tip = 1;
            cin >> v[i].x;
        }
        else
        {
            v[i].tip = 2;
            cin >> v[i].x >> v[i].y, v[i].y--;
        }
    }
    for (int i = 1; i <= q; i++)
    {
        if (v[i].tip == 2)
        {
            vv.push_back({v[i].x, n});
            vv.push_back({v[i].x, v[i].y - 1});
        }
    }
    set<pair<int,int>> scvmax;
    map<pair<int,int>, int> beg;
    int s = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == '0')
        {
            if (s != 0)
            {
                scvmax.insert({s, i - 1});
                s = 0;
            }
            s = 0;
        }
        else
        {
            if (s == 0)
                s = i;
        }
    }
    if (s != 0)
        scvmax.insert({s, n});
    for (int i = 1; i <= q; i++)
    {
        if (v[i].tip == 1)
        {
            int x = v[i].x;
            if (a[x] == '0')
            {
                a[x] = '1';
                bool lft = false, rgt = false;
                if (x != 1 and a[x - 1] == '1')
                    lft = true;
                if (x != n and a[x + 1] == '1')
                    rgt = true;
                if (!lft and !rgt)
                {
                    scvmax.insert({x,x});
                    beg[ {x,x}] = i;
                }
                else if (!lft and rgt)
                {
                    pair<int,int> lol = *scvmax.lower_bound({x + 1, 0});
                    vv.push_back(lol);
                    scvmax.erase(lol);
                    scvmax.insert({x, lol.second});
                    beg[ {x,lol.second}] = i;
                }
                else if (lft and !rgt)
                {
                    pair<int,int> lol = *prev(scvmax.lower_bound({x,0}));
                    vv.push_back(lol);
                    scvmax.erase(lol);
                    scvmax.insert({lol.first, x});
                    beg[ {lol.first,x}] = i;
                }
                else
                {
                    pair<int,int> lolr = *scvmax.lower_bound({x + 1,0}), loll = *prev(scvmax.lower_bound({x,0}));
                    vv.push_back(loll);
                    vv.push_back(lolr);
                    scvmax.erase(loll);
                    scvmax.erase(lolr);
                    scvmax.insert({loll.first, lolr.second});
                    beg[ {loll.first, lolr.second}] = i;
                }
            }
            else
            {
                a[x] = '0';
                pair<int,int> pr = *prev(scvmax.lower_bound({x, n + 1}));
                scvmax.erase(pr);
                vv.push_back(pr);
                if (pr.first != x)
                {
                    scvmax.insert({pr.first, x - 1});
                    beg[ {pr.first, x - 1}] = i;
                }
                if (pr.second != x)
                {
                    scvmax.insert({x + 1, pr.second});
                    beg[ {x + 1, pr.second}] = i;
                }
            }
        }
    }
    build_aib2d_stuff();
    scvmax.clear();
    beg.clear();
    s = 0;
    for (int i = 1; i <= n; i++)
        a[i] = a_ret[i];
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == '0')
        {
            if (s != 0)
            {
                scvmax.insert({s, i - 1});
                s = 0;
            }
            s = 0;
        }
        else
        {
            if (s == 0)
                s = i;
        }
    }
    if (s != 0)
        scvmax.insert({s, n});
    for (int i = 1; i <= q; i++)
    {
        if (v[i].tip == 1)
        {
            int x = v[i].x;
            if (a[x] == '0')
            {
                a[x] = '1';
                bool lft = false, rgt = false;
                if (x != 1 and a[x - 1] == '1')
                    lft = true;
                if (x != n and a[x + 1] == '1')
                    rgt = true;
                if (!lft and !rgt)
                {
                    scvmax.insert({x,x});
                    beg[ {x,x}] = i;
                }
                else if (!lft and rgt)
                {
                    pair<int,int> lol = *scvmax.lower_bound({x + 1, 0});
                    update(lol.first, lol.second, i - beg[lol]);
                    scvmax.erase(lol);
                    scvmax.insert({x, lol.second});
                    beg[ {x,lol.second}] = i;
                }
                else if (lft and !rgt)
                {
                    pair<int,int> lol = *prev(scvmax.lower_bound({x,0}));
                    update(lol.first, lol.second, i - beg[lol]);
                    scvmax.erase(lol);
                    scvmax.insert({lol.first, x});
                    beg[ {lol.first,x}] = i;
                }
                else
                {
                    pair<int,int> lolr = *scvmax.lower_bound({x + 1,0}), loll = *prev(scvmax.lower_bound({x,0}));
                    //cout << loll.first << ' ' << loll.second << ' ' << lolr.first << ' ' << lolr.second << endl;
                    update(loll.first, loll.second, i - beg[loll]);
                    update(lolr.first, lolr.second, i - beg[lolr]);
                    scvmax.erase(loll);
                    scvmax.erase(lolr);
                    scvmax.insert({loll.first, lolr.second});
                    beg[ {loll.first, lolr.second}] = i;
                }
            }
            else
            {
                a[x] = '0';
                pair<int,int> pr = *prev(scvmax.lower_bound({x, n + 1}));
                scvmax.erase(pr);
                update(pr.first, pr.second, i - beg[pr]);
                if (pr.first != x)
                {
                    scvmax.insert({pr.first, x - 1});
                    beg[ {pr.first, x - 1}] = i;
                }
                if (pr.second != x)
                {
                    scvmax.insert({x + 1, pr.second});
                    beg[ {x + 1, pr.second}] = i;
                }
            }
        }
        else
        {
            int x = v[i].x, y = v[i].y;
            int vl = query(x, n) - query(x, y - 1);
            if (a[x] == '1')
            {
                pair<int,int> pr = *prev(scvmax.lower_bound({x, n + 1}));
                //cout << i << ' ' << pr.first << ' ' << pr.second << endl;
                if (pr.first <= x and pr.second >= y)
                    vl += i - beg[pr];
            }
            cout << vl << '\n';
        }
    }
    return 0;
}

/**
Ma uit la secventele maximale de 1, eu vreau sa vad in cate momente a fost [x y] inclus intr-o secventa maximala
Daca retin, pentru fiecare secventa maximala, cat dureaza (termin cu ea cand se modifica), vreau suma(timp) pentru secventele care ma includ
Sa zicem ca atunci cand modific o secventa maximala o pun in "DS", o sa adun la raspuns, daca acum sunt intr-o secventa maximala, de cand e ea
Si fac O(N + Q) update-uri de forma: pentru fiecare (x, y) cu L <= x <= y <= R, adauga k si Q query-uri de forma: zi cat e un punct
Adica tehnic bag update cu +k in (L,R), si vreau suma pe dreptunghiul ((1,y), (x, N)) adica ((1,1), (x,N)) - ((1,1), (x, y - 1))
Yayy, aib 2d pe care nu l-am mai implementat vreodata
**/

Compilation message

street_lamps.cpp: In function 'int get_pos(int, int)':
street_lamps.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if (st + pas < ps[unde].size() and ps[unde][st + pas] <= y)
      |             ~~~~~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void update(int, int, int)':
street_lamps.cpp:57:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int j = get_pos(i,y); j < ps[i].size(); j += (j & -j))
      |                                    ~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15704 KB Output is correct
2 Correct 4 ms 14424 KB Output is correct
3 Correct 4 ms 15704 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 5 ms 15708 KB Output is correct
6 Correct 4 ms 15796 KB Output is correct
7 Correct 5 ms 14512 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 22464 KB Output is correct
2 Correct 258 ms 26128 KB Output is correct
3 Correct 456 ms 29632 KB Output is correct
4 Correct 1642 ms 89988 KB Output is correct
5 Correct 1761 ms 90888 KB Output is correct
6 Correct 1494 ms 90788 KB Output is correct
7 Correct 818 ms 76468 KB Output is correct
8 Correct 832 ms 77840 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15964 KB Output is correct
2 Correct 8 ms 14684 KB Output is correct
3 Correct 5 ms 15964 KB Output is correct
4 Correct 5 ms 14656 KB Output is correct
5 Correct 1658 ms 92056 KB Output is correct
6 Correct 1779 ms 98768 KB Output is correct
7 Correct 1764 ms 101280 KB Output is correct
8 Correct 1289 ms 91044 KB Output is correct
9 Correct 122 ms 25532 KB Output is correct
10 Correct 130 ms 29384 KB Output is correct
11 Correct 141 ms 29380 KB Output is correct
12 Correct 1198 ms 89648 KB Output is correct
13 Correct 1183 ms 91052 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15960 KB Output is correct
2 Correct 6 ms 14684 KB Output is correct
3 Correct 6 ms 15964 KB Output is correct
4 Correct 5 ms 15964 KB Output is correct
5 Correct 1355 ms 93364 KB Output is correct
6 Correct 1522 ms 97808 KB Output is correct
7 Correct 1558 ms 96060 KB Output is correct
8 Correct 1780 ms 91060 KB Output is correct
9 Correct 300 ms 25796 KB Output is correct
10 Correct 249 ms 25076 KB Output is correct
11 Correct 330 ms 25572 KB Output is correct
12 Correct 227 ms 25072 KB Output is correct
13 Correct 314 ms 25804 KB Output is correct
14 Correct 230 ms 25080 KB Output is correct
15 Correct 1248 ms 89564 KB Output is correct
16 Correct 1258 ms 91104 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15704 KB Output is correct
2 Correct 4 ms 14424 KB Output is correct
3 Correct 4 ms 15704 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 5 ms 15708 KB Output is correct
6 Correct 4 ms 15796 KB Output is correct
7 Correct 5 ms 14512 KB Output is correct
8 Correct 206 ms 22464 KB Output is correct
9 Correct 258 ms 26128 KB Output is correct
10 Correct 456 ms 29632 KB Output is correct
11 Correct 1642 ms 89988 KB Output is correct
12 Correct 1761 ms 90888 KB Output is correct
13 Correct 1494 ms 90788 KB Output is correct
14 Correct 818 ms 76468 KB Output is correct
15 Correct 832 ms 77840 KB Output is correct
16 Correct 5 ms 15964 KB Output is correct
17 Correct 8 ms 14684 KB Output is correct
18 Correct 5 ms 15964 KB Output is correct
19 Correct 5 ms 14656 KB Output is correct
20 Correct 1658 ms 92056 KB Output is correct
21 Correct 1779 ms 98768 KB Output is correct
22 Correct 1764 ms 101280 KB Output is correct
23 Correct 1289 ms 91044 KB Output is correct
24 Correct 122 ms 25532 KB Output is correct
25 Correct 130 ms 29384 KB Output is correct
26 Correct 141 ms 29380 KB Output is correct
27 Correct 1198 ms 89648 KB Output is correct
28 Correct 1183 ms 91052 KB Output is correct
29 Correct 5 ms 15960 KB Output is correct
30 Correct 6 ms 14684 KB Output is correct
31 Correct 6 ms 15964 KB Output is correct
32 Correct 5 ms 15964 KB Output is correct
33 Correct 1355 ms 93364 KB Output is correct
34 Correct 1522 ms 97808 KB Output is correct
35 Correct 1558 ms 96060 KB Output is correct
36 Correct 1780 ms 91060 KB Output is correct
37 Correct 300 ms 25796 KB Output is correct
38 Correct 249 ms 25076 KB Output is correct
39 Correct 330 ms 25572 KB Output is correct
40 Correct 227 ms 25072 KB Output is correct
41 Correct 314 ms 25804 KB Output is correct
42 Correct 230 ms 25080 KB Output is correct
43 Correct 1248 ms 89564 KB Output is correct
44 Correct 1258 ms 91104 KB Output is correct
45 Correct 97 ms 24012 KB Output is correct
46 Correct 137 ms 24240 KB Output is correct
47 Correct 818 ms 57020 KB Output is correct
48 Correct 1673 ms 97472 KB Output is correct
49 Correct 145 ms 29876 KB Output is correct
50 Correct 141 ms 29636 KB Output is correct
51 Correct 155 ms 29896 KB Output is correct
52 Correct 173 ms 30152 KB Output is correct
53 Correct 170 ms 30148 KB Output is correct
54 Correct 175 ms 30148 KB Output is correct