oj.uz

Submission #440492

# Submission time Handle Problem Language Result Execution time Memory
440492 2021-07-02T10:23:12 Z VladM Street Lamps (APIO19_street_lamps) C++14
40 / 100
 820 ms 11628 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-1);
        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 1 ms 204 KB Output is correct
2 Correct 0 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 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 6564 KB Output is correct
2 Correct 463 ms 6528 KB Output is correct
3 Correct 486 ms 6660 KB Output is correct
4 Correct 536 ms 10412 KB Output is correct
5 Correct 588 ms 10664 KB Output is correct
6 Correct 466 ms 10260 KB Output is correct
7 Correct 771 ms 10260 KB Output is correct
8 Correct 820 ms 11628 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 1 ms 204 KB Output is correct
2 Correct 0 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 204 KB Output is correct
8 Correct 484 ms 6564 KB Output is correct
9 Correct 463 ms 6528 KB Output is correct
10 Correct 486 ms 6660 KB Output is correct
11 Correct 536 ms 10412 KB Output is correct
12 Correct 588 ms 10664 KB Output is correct
13 Correct 466 ms 10260 KB Output is correct
14 Correct 771 ms 10260 KB Output is correct
15 Correct 820 ms 11628 KB Output is correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Halted 0 ms 0 KB -