oj.uz

Submission #742666

# Submission time Handle Problem Language Result Execution time Memory
742666 2023-05-16T16:41:20 Z speedyArda Street Lamps (APIO19_street_lamps) C++14
40 / 100
 282 ms 28628 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 if(ltog < fque) // Subtask 4
        { 
            
        } else //Subtask 3  
        {
            for(int i = 1; i <= q; i++)
            {
                if(queries[i].first == "toggle")
                {
                    upd(queries[i].second.first, i);
                } else 
                {
                    int fi = get(queries[i].second.first, queries[i].second.second);
                    if(fi == 1e9)
                        cout << "0\n";
                    else
                        cout << i - fi << "\n";
                }
            }
        }
    }
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 24704 KB Output is correct
2 Correct 183 ms 24620 KB Output is correct
3 Correct 192 ms 24692 KB Output is correct
4 Correct 237 ms 27312 KB Output is correct
5 Correct 231 ms 27696 KB Output is correct
6 Correct 213 ms 27252 KB Output is correct
7 Correct 282 ms 27220 KB Output is correct
8 Correct 271 ms 28628 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23672 KB Output is correct
4 Correct 13 ms 23852 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 13 ms 23692 KB Output is correct
8 Correct 169 ms 24704 KB Output is correct
9 Correct 183 ms 24620 KB Output is correct
10 Correct 192 ms 24692 KB Output is correct
11 Correct 237 ms 27312 KB Output is correct
12 Correct 231 ms 27696 KB Output is correct
13 Correct 213 ms 27252 KB Output is correct
14 Correct 282 ms 27220 KB Output is correct
15 Correct 271 ms 28628 KB Output is correct
16 Correct 13 ms 23764 KB Output is correct
17 Incorrect 13 ms 23764 KB Output isn't correct
18 Halted 0 ms 0 KB -