oj.uz

답안 #724528

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
724528 2023-04-15T13:35:27 Z n0sk1ll 가로등 (APIO19_street_lamps) C++14
40 / 100
 1414 ms 80288 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)
{
    exit(0);
}

const int N=6'000'005;
int val[N],L[N],R[N];
int idx=0;

void add(int p, int q, int l, int r, int s, int x)
{
    val[p]=val[q]+x;
    if (l==r) return;

    int mid=(l+r)/2;
    if (s<=mid) L[p]=++idx,R[p]=R[q],add(L[p],L[q],l,mid,s,x);
    else L[p]=L[q],R[p]=++idx,add(R[p],R[q],mid+1,r,s,x);
}

int sum(int p, int l, int r, int ll, int rr)
{
    if (!p || ll>r || rr<l) return 0;
    if (ll<=l && rr>=r) return val[p];
    int mid=(l+r)/2;
    return sum(L[p],l,mid,ll,rr)+sum(R[p],mid+1,r,ll,rr);
}

int root[300005];

void solvepersistent(int n, string &s, int q, vector<pii> &qrys)
{
    ++idx; //obezbedimo root - 1
    int temp;
    ff(i,0,n) if (s[i]=='1') temp=++idx,add(temp,root[0],0,n-1,i,1),root[0]=temp;

    ff(i,0,q)
    {
        root[i+1]=root[i];
        int a=qrys[i].xx,b=qrys[i].yy;
        if (a==-1) root[i+1]=++idx,add(root[i+1],root[i],0,n-1,b-1,s[b-1]=='1'?-1:1),s[b-1]='0'+'1'-s[b-1];
        else
        {
            int l=-1,r=i+1;
            while (r-l>1)
            {
                int mid=(l+r)/2;
                if (sum(root[mid],0,n-1,a-1,b-2)<b-a) l=mid;
                else r=mid;
            }
            cout<<(i+1)-r<<"\n";
        }
    }
}

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 && (int)qrys.size()<=100) solvebrute(n,s,(int)qrys.size(),qrys);
    else if (!imaoff) solvepersistent(n,s,(int)qrys.size(),qrys);
    else if (susedni) solvepoints(n,s,(int)qrys.size(),qrys);
}

//Note to self: Check for overflow

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 4500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 198 ms 72156 KB Output is correct
6 Correct 858 ms 72384 KB Output is correct
7 Correct 1241 ms 72580 KB Output is correct
8 Correct 1414 ms 74180 KB Output is correct
9 Correct 284 ms 4164 KB Output is correct
10 Correct 301 ms 7596 KB Output is correct
11 Correct 337 ms 7740 KB Output is correct
12 Correct 124 ms 10996 KB Output is correct
13 Correct 1409 ms 80288 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 68 ms 4500 KB Output isn't correct
9 Halted 0 ms 0 KB -