oj.uz

Submission #931492

# Submission time Handle Problem Language Result Execution time Memory
931492 2024-02-21T23:33:07 Z Ice_man Street Lamps (APIO19_street_lamps) C++14
100 / 100
 1987 ms 111292 KB 
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <set>

#define maxn 300005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;

std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}

struct que
{
    int type , l , r;

    que(){};
    que(int _type , int _l , int _r)
    {
        type = _type;
        l = _l;
        r = _r;
    }
};

vector <que> queries;

vector <int> v[maxn], fenwick[maxn];
int n, q;

void update(int line, int to, int val)
{
    ///cout << line << " " << to << " " << val << endl;

    for(int i = line; i <= n; i += (i & -i))
    {
        //if(v[i].size() == 0)
          //  continue;

        auto it = upper_bound(v[i].begin(), v[i].end(), to);

        for(int j = it - v[i].begin(); j <= v[i].size(); j += (j & -j))
            fenwick[i][j] += val;
    }
}


int query(int line, int to)
{
    //cout << "_--_ " << line << " " << to << endl;

    int ans = 0;

    for(int i = line; i > 0; i -= (i & -i))
    {
        //if(v[i].size() == 0)
          //  continue;

        auto it = upper_bound(v[i].begin(), v[i].end(), to);

        for(int j = it - v[i].begin(); j > 0; j -= (j & -j))
            ans += fenwick[i][j];

    }

    return ans;
}


void add(int line, int to)
{
    //cout << line << " " << to << endl;

    for(int i = line; i <= n; i += (i & -i))
        v[i].pb(to);
}

string s;

set <int> zeros;

int xo[maxn], ans[maxn];

void read()
{
    cin >> n >> q;
    cin >> s;

    queries.resize(q + 1);

    zeros.insert(0);
    zeros.insert(n + 1);

    for(int i = 1; i <= n; i++)
    {
        xo[i] = s[i - 1] - '0';
        if(!xo[i])
            zeros.insert(i);
    }

}


pair <int , int> timer[maxn];

void pre_solve()
{
    string type;
    int a , b;

    for(int i = 1; i <= q; i++)
    {
        cin >> type;

        if(type == "toggle")
        {
            cin >> a;

            xo[a] ^= 1;

            if(xo[a] != 0)
                zeros.erase(zeros.find(a));
            else
                zeros.insert(a);

            auto it = zeros.upper_bound(a);
            int pom = *it - 1;

            it--;
            if(*it == a)
                it--;

            int pom2 = *it + 1;

            add(pom2 , a);
            add(pom2 , pom + 1);
            add(a + 1 , a);
            add(a + 1 , pom + 1);

            queries[i] = {0 , pom2 , pom};

            timer[i] = {a , (xo[a]? -i : i)};

            continue;
        }

        cin >> a >> b;
        b--;

        queries[i] = {1 , a , b};
        if(*zeros.lower_bound(a) > b)
            ans[i] += i;

    }

    for(int i = 1; i <= n; i++)
    {
        sort(v[i].begin() , v[i].end());

        v[i].resize(unique(v[i].begin() , v[i].end()) - v[i].begin());
        fenwick[i].resize(v[i].size() + 1);
    }

}


void solve()
{
    /**for(int i = 1; i <= q; i++)
        cout << timer[i].X << " - " << timer[i].Y << endl;*/

    int t , l , r;

    for(int i = 1; i <= q; i++)
    {
        t = queries[i].type;
        l = queries[i].l;
        r = queries[i].r;

        if(t == 0)
        {
            update(l , timer[i].X , timer[i].Y);
            update(l , r + 1 , -timer[i].Y);
            update(timer[i].X + 1 , timer[i].X , -timer[i].Y);
            update(timer[i].X + 1 , r + 1 , timer[i].Y);
        }
        else cout << query(l , r) + ans[i] << endl;
    }
}



int main()
{

    /**#ifdef ONLINE_JUDGE
        freopen("taxi.in", "r", stdin);
        freopen("taxi.out", "w", stdout);
    #endif*/

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    //startT = std::chrono::high_resolution_clock::now();

    read();
    pre_solve();
    solve();


    return 0;
}

Compilation message

street_lamps.cpp: In function 'void update(int, int, int)':
street_lamps.cpp:62:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int j = it - v[i].begin(); j <= v[i].size(); j += (j & -j))
      |                                        ~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16984 KB Output is correct
2 Correct 4 ms 16984 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16984 KB Output is correct
6 Correct 4 ms 16984 KB Output is correct
7 Correct 4 ms 17240 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 34312 KB Output is correct
2 Correct 253 ms 39352 KB Output is correct
3 Correct 459 ms 46184 KB Output is correct
4 Correct 1116 ms 83652 KB Output is correct
5 Correct 955 ms 68696 KB Output is correct
6 Correct 1253 ms 93052 KB Output is correct
7 Correct 245 ms 50664 KB Output is correct
8 Correct 106 ms 38164 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17240 KB Output is correct
2 Correct 5 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 5 ms 16988 KB Output is correct
5 Correct 1987 ms 105504 KB Output is correct
6 Correct 1456 ms 91636 KB Output is correct
7 Correct 891 ms 68056 KB Output is correct
8 Correct 98 ms 38112 KB Output is correct
9 Correct 62 ms 25484 KB Output is correct
10 Correct 73 ms 26196 KB Output is correct
11 Correct 70 ms 26188 KB Output is correct
12 Correct 234 ms 50664 KB Output is correct
13 Correct 98 ms 38040 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 17244 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 5 ms 16988 KB Output is correct
4 Correct 6 ms 16988 KB Output is correct
5 Correct 252 ms 44252 KB Output is correct
6 Correct 749 ms 70164 KB Output is correct
7 Correct 1264 ms 92360 KB Output is correct
8 Correct 1860 ms 111292 KB Output is correct
9 Correct 323 ms 49584 KB Output is correct
10 Correct 278 ms 46496 KB Output is correct
11 Correct 323 ms 51060 KB Output is correct
12 Correct 276 ms 46908 KB Output is correct
13 Correct 318 ms 50208 KB Output is correct
14 Correct 280 ms 46900 KB Output is correct
15 Correct 238 ms 50660 KB Output is correct
16 Correct 101 ms 38120 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16984 KB Output is correct
2 Correct 4 ms 16984 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16984 KB Output is correct
6 Correct 4 ms 16984 KB Output is correct
7 Correct 4 ms 17240 KB Output is correct
8 Correct 197 ms 34312 KB Output is correct
9 Correct 253 ms 39352 KB Output is correct
10 Correct 459 ms 46184 KB Output is correct
11 Correct 1116 ms 83652 KB Output is correct
12 Correct 955 ms 68696 KB Output is correct
13 Correct 1253 ms 93052 KB Output is correct
14 Correct 245 ms 50664 KB Output is correct
15 Correct 106 ms 38164 KB Output is correct
16 Correct 6 ms 17240 KB Output is correct
17 Correct 5 ms 16988 KB Output is correct
18 Correct 4 ms 16988 KB Output is correct
19 Correct 5 ms 16988 KB Output is correct
20 Correct 1987 ms 105504 KB Output is correct
21 Correct 1456 ms 91636 KB Output is correct
22 Correct 891 ms 68056 KB Output is correct
23 Correct 98 ms 38112 KB Output is correct
24 Correct 62 ms 25484 KB Output is correct
25 Correct 73 ms 26196 KB Output is correct
26 Correct 70 ms 26188 KB Output is correct
27 Correct 234 ms 50664 KB Output is correct
28 Correct 98 ms 38040 KB Output is correct
29 Correct 5 ms 17244 KB Output is correct
30 Correct 4 ms 16988 KB Output is correct
31 Correct 5 ms 16988 KB Output is correct
32 Correct 6 ms 16988 KB Output is correct
33 Correct 252 ms 44252 KB Output is correct
34 Correct 749 ms 70164 KB Output is correct
35 Correct 1264 ms 92360 KB Output is correct
36 Correct 1860 ms 111292 KB Output is correct
37 Correct 323 ms 49584 KB Output is correct
38 Correct 278 ms 46496 KB Output is correct
39 Correct 323 ms 51060 KB Output is correct
40 Correct 276 ms 46908 KB Output is correct
41 Correct 318 ms 50208 KB Output is correct
42 Correct 280 ms 46900 KB Output is correct
43 Correct 238 ms 50660 KB Output is correct
44 Correct 101 ms 38120 KB Output is correct
45 Correct 83 ms 28540 KB Output is correct
46 Correct 126 ms 30660 KB Output is correct
47 Correct 550 ms 51528 KB Output is correct
48 Correct 1137 ms 83056 KB Output is correct
49 Correct 74 ms 26708 KB Output is correct
50 Correct 71 ms 26560 KB Output is correct
51 Correct 72 ms 26704 KB Output is correct
52 Correct 72 ms 26960 KB Output is correct
53 Correct 78 ms 27108 KB Output is correct
54 Correct 70 ms 26928 KB Output is correct