oj.uz

Submission #440489

# Submission time Handle Problem Language Result Execution time Memory
440489 2021-07-02T10:21:41 Z VladM Street Lamps (APIO19_street_lamps) C++14
40 / 100
 806 ms 11740 KB 
#include <bits/stdc++.h>

using namespace std;

#define DIM 300007

#define INF 1000000007

struct Q
{
    int r, a, b;
};

vector<Q> quer;

long long n, q, nom, it, flag, a, b, res;

string s[107], r;

void solve1(string st)
{
    s[0]=st;
    s[0]='&'+s[0];
    nom=0;
    for(int h=1; h<=q; h++)
    {
        if(quer[h].r==1) r="t";
        else r="s";
        if(r[0]=='t')
        {
            it=quer[h].a;
            nom++;
            s[nom]=s[nom-1];
            if(s[nom][it]=='0') s[nom][it]='1';
            else s[nom][it]='0';
            continue;
        }
        a=quer[h].a;
        b=quer[h].b;
        res=0;
        for(int k=0; k<=nom; k++)
        {
            flag=0;
            for(int i=a; i<b; i++)
            {
                if(s[k][i]=='0')
                {
                    flag=1;
                    break;
                }
            }
            if(flag==0) res++;
        }
        nom++;
        s[nom]=s[nom-1];
        cout<<res<<endl;
    }
    return;
}

void solve2(string st)
{
    string s, r;
    long long a, b, it;
    vector<long long> lst, ans;
    lst.resize(n+7);
    ans.resize(n+7);
    s=st;
    s='&'+s;
    for(int i=1; i<=n; i++)  lst[i]=0;
    for(int i=1; i<=q; i++)
    {
        if(quer[i].r==1) r="t";
        else r="s";
        if(r[0]=='t')
        {
            it=quer[i].a;
            if(s[it]=='1') ans[it]+=i-lst[it];
            if(s[it]=='1') s[it]='0';
            else s[it]='1';
            lst[it]=i;
            continue;
        }
        a=quer[i].a;
        b=quer[i].b;
        if(s[a]=='1') ans[a]+=i-lst[a];
        lst[a]=i;
        cout<<ans[a]<<endl;
    }
    return;
}

int t[4*DIM];

void BuildTree(int v, int tl, int tr, string &s)
{
    if(tl==tr)
    {
        if(s[tl]=='1') t[v]=0;
        else t[v]=INF;
        return;
    }
    int tm=(tl+tr)>>1;
    BuildTree(2*v+1, tl, tm, s);
    BuildTree(2*v+2, tm+1, tr, s);
    t[v]=max(t[2*v+1], t[2*v+2]);
    return;
}

void update(int v, int tl, int tr, int x, int val)
{
    if(x<tl || tr<x) return;
    if(tl==tr)
    {
        t[v]=val;
        return;
    }
    int tm=(tl+tr)>>1;
    update(2*v+1, tl, tm, x, val);
    update(2*v+2, tm+1, tr, x, val);
    t[v]=max(t[2*v+1], t[2*v+2]);
    return;
}

int get_max(int v, int tl, int tr, int L, int R)
{
    if(R<tl || tr<L) return -INF;
    if(L<=tl && tr<=R) return t[v];
    int tm=(tl+tr)>>1;
    int mx1=get_max(2*v+1, tl, tm, L, R);
    int mx2=get_max(2*v+2, tm+1, tr, L, R);
    return max(mx1, mx2);
}

void solve3(string st)
{
    string s='&'+st;
    BuildTree(0, 1, n, s);
    for(int i=1; i<=q; i++)
    {
        if(quer[i].r==1)
        {
            update(0, 1, n, quer[i].a, i);
            continue;
        }
        int a, b;
        a=quer[i].a;
        b=quer[i].b;
        int mx=get_max(0, 1, n, a, b);
        if(mx==INF) cout<<0<<endl;
        cout<<i-mx<<endl;
    }
}

int main()
{
    cin>>n>>q;
    cin>>s[0];
    quer.push_back({0, 0, 0});
    for(int i=1; i<=q; i++)
    {
        cin>>r;
        if(r[0]=='t')
        {
            cin>>it;
            quer.push_back({1, it, 0});
            continue;
        }
        cin>>a>>b;
        if(b-a!=1) flag=1;
        quer.push_back({2, a, b});
    }
    if(n<=100 && q<=100) solve1(s[0]);
    else if(flag==0) solve2(s[0]);
    else solve3(s[0]);
    return 0;
}

Compilation message

street_lamps.cpp: In function 'void solve2(std::string)':
street_lamps.cpp:64:18: warning: variable 'b' set but not used [-Wunused-but-set-variable]
   64 |     long long a, b, it;
      |                  ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:166:32: warning: narrowing conversion of 'it' from 'long long int' to 'int' [-Wnarrowing]
  166 |             quer.push_back({1, it, 0});
      |                                ^~
street_lamps.cpp:171:28: warning: narrowing conversion of 'a' from 'long long int' to 'int' [-Wnarrowing]
  171 |         quer.push_back({2, a, b});
      |                            ^
street_lamps.cpp:171:31: warning: narrowing conversion of 'b' from 'long long int' to 'int' [-Wnarrowing]
  171 |         quer.push_back({2, a, b});
      |                               ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 320 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 6456 KB Output is correct
2 Correct 460 ms 6544 KB Output is correct
3 Correct 479 ms 6568 KB Output is correct
4 Correct 517 ms 10316 KB Output is correct
5 Correct 558 ms 10620 KB Output is correct
6 Correct 449 ms 10240 KB Output is correct
7 Correct 763 ms 10304 KB Output is correct
8 Correct 806 ms 11740 KB Output is correct

Subtask #3
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 #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 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 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 427 ms 6456 KB Output is correct
9 Correct 460 ms 6544 KB Output is correct
10 Correct 479 ms 6568 KB Output is correct
11 Correct 517 ms 10316 KB Output is correct
12 Correct 558 ms 10620 KB Output is correct
13 Correct 449 ms 10240 KB Output is correct
14 Correct 763 ms 10304 KB Output is correct
15 Correct 806 ms 11740 KB Output is correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Halted 0 ms 0 KB -