oj.uz

Submission #742674

# Submission time Handle Problem Language Result Execution time Memory
742674 2023-05-16T16:50:57 Z speedyArda Street Lamps (APIO19_street_lamps) C++14
40 / 100
 304 ms 28712 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 <= 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";
                }
            }
        }
    }
}

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 23764 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23784 KB Output is correct
7 Correct 12 ms 23736 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 24780 KB Output is correct
2 Correct 194 ms 24668 KB Output is correct
3 Correct 215 ms 24720 KB Output is correct
4 Correct 242 ms 27324 KB Output is correct
5 Correct 271 ms 27712 KB Output is correct
6 Correct 220 ms 27316 KB Output is correct
7 Correct 285 ms 27212 KB Output is correct
8 Correct 304 ms 28712 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23728 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 23764 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23784 KB Output is correct
7 Correct 12 ms 23736 KB Output is correct
8 Correct 182 ms 24780 KB Output is correct
9 Correct 194 ms 24668 KB Output is correct
10 Correct 215 ms 24720 KB Output is correct
11 Correct 242 ms 27324 KB Output is correct
12 Correct 271 ms 27712 KB Output is correct
13 Correct 220 ms 27316 KB Output is correct
14 Correct 285 ms 27212 KB Output is correct
15 Correct 304 ms 28712 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 14 ms 23764 KB Output is correct
18 Correct 13 ms 23764 KB Output is correct
19 Incorrect 12 ms 23764 KB Output isn't correct
20 Halted 0 ms 0 KB -