oj.uz

Submission #724518

# Submission time Handle Problem Language Result Execution time Memory
724518 2023-04-15T13:06:38 Z n0sk1ll Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 9704 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

void solvebrute(int n, string &s, int q, vector<pii> &qrys)
{
    vector<string> verzije;
    verzije.pb(s);

    for (auto it : qrys)
    {
        if (it.xx>-1)
        {
            int kolko=0;
            for (auto s : verzije)
            {
                bool moze=true;
                ff(i,it.xx-1,it.yy-1) if (s[i]=='0') moze=false;
                if (moze) kolko++;
            }
            cout<<kolko<<"\n";
        }
        verzije.pb(verzije.back());
        if (it.xx==-1) verzije.back()[it.yy-1]='0'+'1'-verzije.back()[it.yy-1];
    }
}

void solvepoints(int n, string &s, int q, vector<pii> &qrys)
{

}

void solvepersistent(int n, string &s, int q, vector<pii> &qrys)
{

}

int main()
{
    FAST;

    int n,q; cin>>n>>q;
    string s; cin>>s;
    vector<bool> pomcina(n+3,0);

    bool susedni=true;
    bool imaoff=false;

    vector<pii> qrys; //a,b znaci a,b;  -1,i znaci toggle i
    while (q--)
    {
        string tip; cin>>tip;
        if (tip=="toggle")
        {
            int i; cin>>i;
            qrys.pb({-1,i});
            if (s[i-1]=='1' || pomcina[i-1]) imaoff=true;
            pomcina[i-1]=true;
        }
        else
        {
            int a,b; cin>>a>>b;
            qrys.pb({a,b});
            if (b-a>1) susedni=false;
        }
    }

    if (n<=100 && q<=100) solvebrute(n,s,q,qrys);
    else if (susedni) solvepoints(n,s,q,qrys);
    else if (!imaoff) solvepersistent(n,s,q,qrys);
}

//Note to self: Check for overflow

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5075 ms 9704 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Execution timed out 5075 ms 9704 KB Time limit exceeded
9 Halted 0 ms 0 KB -