oj.uz

Submission #742675

# Submission time Handle Problem Language Result Execution time Memory
742675 2023-05-16T16:52:17 Z speedyArda Street Lamps (APIO19_street_lamps) C++14
60 / 100
 343 ms 32340 KB 
#include "bits/stdc++.h"

using namespace std;
const int MAXN = 3e5+5;
vector<int> seg(MAXN * 2, 1e9);
int n, q;
void upd(int v, int val)
{
    for(seg[v += n] = val; v > 1; v >>= 1)
    {
        seg[v >> 1] = max(seg[v],seg[v ^ 1]);
    }
}

int get(int l, int r)
{
    int val = 0;
    for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
    {
        if(l & 1)
            val = max(val, seg[l++]);
        if(r & 1)   
            val = max(val, seg[--r]);
    }
    return val;
}
vector< pair<string, pair<int, int> > > queries(MAXN); 
string stats[MAXN];
int main() 
{
    cin >> n >> q;
    string in;
    cin >> in;
    in = " " + in;
    stats[0] = in;
    int maxdiff = 0;
    int ltog = 0, fque = 1e9;
    for(int i = 1; i <= q; i++)
    {
        cin >> queries[i].first;
        if(queries[i].first == "toggle")
        {
            cin >> queries[i].second.first;
            ltog = i;
        } else {
            cin  >> queries[i].second.first >> queries[i].second.second; 
            maxdiff = max(maxdiff, queries[i].second.second - queries[i].second.first);
            fque = min(fque, i);
        }
    }
    if(max(n, q) <= 100) // Subtask 1
    {
        for(int i = 1; i <= q; i++)
        {
            if(queries[i].first == "toggle")
            {
                in[queries[i].second.first] = (in[queries[i].second.first] == '1' ? '0' : '1');
                stats[i] = in;
            } else 
            {
                stats[i] = in;
                int pos = 0;
                for(int ava = 0; ava < i; ava++) {
                    string temp = stats[ava];
                    int beg = queries[i].second.first;
                    int end = queries[i].second.second;
                    while(beg < end)
                    {

                        if(temp[beg] == '1')
                            beg++;
                        else
                            break;
                    }
                    if(beg == end)
                        pos++;
                }

               cout << pos << "\n";

            }

        }
    } else 
    {
        if(maxdiff == 1) // Subtask 2
        {
            vector<int> roads(n+5, 0);
            vector<int> last(n+5, 0);
            
            for(int i = 1; i <= q; i++)
            {
                int idx = queries[i].second.first;
                if(queries[i].first == "toggle")
                {
                    if(in[idx] == '1')
                    {
                        roads[idx] += i - last[idx];
                        in[idx] = '0';
                    } else 
                    {
                        last[idx] = i;
                        in[idx] = '1';
                    }
                } else 
                {
                    int val = roads[idx];
                    if(in[idx] == '1')
                    {
                        val += i - last[idx];
                    }
                    cout << val << "\n";
                }
            }
        } else //Subtask 3  
        {
            for(int i = 1; i <= n; i++)
            {
                if(in[i] == '1') {
                    upd(i, 1);
                }
            }
            for(int i = 1; i <= q; i++)
            {
                if(queries[i].first == "toggle")
                {
                    upd(queries[i].second.first, i + 1);
                } else 
                {
                    int fi = get(queries[i].second.first, queries[i].second.second - 1);
                    if(fi == 1e9)
                        cout << "0\n";
                    else
                        cout << i - fi + 1 << "\n";
                }
            }
        }
    }
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:37:9: warning: variable 'ltog' set but not used [-Wunused-but-set-variable]
   37 |     int ltog = 0, fque = 1e9;
      |         ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23800 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23704 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 24668 KB Output is correct
2 Correct 179 ms 24652 KB Output is correct
3 Correct 196 ms 24692 KB Output is correct
4 Correct 245 ms 27348 KB Output is correct
5 Correct 236 ms 27752 KB Output is correct
6 Correct 230 ms 27308 KB Output is correct
7 Correct 278 ms 27308 KB Output is correct
8 Correct 295 ms 28600 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23688 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 13 ms 23776 KB Output is correct
4 Correct 12 ms 23736 KB Output is correct
5 Correct 190 ms 28524 KB Output is correct
6 Correct 224 ms 29248 KB Output is correct
7 Correct 283 ms 29988 KB Output is correct
8 Correct 320 ms 32300 KB Output is correct
9 Correct 180 ms 27352 KB Output is correct
10 Correct 178 ms 27724 KB Output is correct
11 Correct 188 ms 27868 KB Output is correct
12 Correct 297 ms 30872 KB Output is correct
13 Correct 343 ms 32340 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23804 KB Output is correct
2 Incorrect 12 ms 23752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23800 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23704 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 181 ms 24668 KB Output is correct
9 Correct 179 ms 24652 KB Output is correct
10 Correct 196 ms 24692 KB Output is correct
11 Correct 245 ms 27348 KB Output is correct
12 Correct 236 ms 27752 KB Output is correct
13 Correct 230 ms 27308 KB Output is correct
14 Correct 278 ms 27308 KB Output is correct
15 Correct 295 ms 28600 KB Output is correct
16 Correct 12 ms 23688 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 13 ms 23776 KB Output is correct
19 Correct 12 ms 23736 KB Output is correct
20 Correct 190 ms 28524 KB Output is correct
21 Correct 224 ms 29248 KB Output is correct
22 Correct 283 ms 29988 KB Output is correct
23 Correct 320 ms 32300 KB Output is correct
24 Correct 180 ms 27352 KB Output is correct
25 Correct 178 ms 27724 KB Output is correct
26 Correct 188 ms 27868 KB Output is correct
27 Correct 297 ms 30872 KB Output is correct
28 Correct 343 ms 32340 KB Output is correct
29 Correct 12 ms 23804 KB Output is correct
30 Incorrect 12 ms 23752 KB Output isn't correct
31 Halted 0 ms 0 KB -