oj.uz

Submission #432953

# Submission time Handle Problem Language Result Execution time Memory
432953 2021-06-18T15:35:50 Z TLP39 Street Lamps (APIO19_street_lamps) C++14
40 / 100
 359 ms 16484 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;

struct query{
    int t,u,v;
};

const int big=1000000000;

int n,q;
bool on[300010];
int last_open[300010]={};
char s[300010];
int res[300010]={};
int ans;
int seg[1200040]={};
int x,y;
vector<query> vec;
void upd(int v,int l,int r,int pos,int val)
{
    if(l==r)
    {
        seg[v]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=pos) upd(v<<1,l,mid,pos,val);
    else upd(1+(v<<1),mid+1,r,pos,val);
    seg[v]=max(seg[v<<1],seg[1+(v<<1)]);
}

int que(int v,int l,int r,int st,int ed)
{
    if(st>ed) return -1;
    if(l==st && r==ed) return seg[v];
    int mid=(l+r)>>1;
    return max(que(v<<1,l,mid,st,min(mid,ed)),que(1+(v<<1),mid+1,r,max(mid+1,st),ed));
}

void solve_2()
{
    int temp;
    for(int i=0;i<n;i++) on[i+1]=(s[i]=='1');
    for(int i=0;i<q;i++)
    {
        if(vec[i].t==1)
        {
            temp=vec[i].u;
            if(on[temp]) printf("%d\n",res[temp]+(i+1-last_open[temp]));
            else printf("%d\n",res[temp]);
        }
        else
        {
            temp=vec[i].u;
            if(on[temp])
            {
                on[temp]=false;
                res[temp]+=((i+1)-last_open[temp]);
            }
            else
            {
                on[temp]=true;
                last_open[temp]=i+1;
            }
        }
    }
}

void solve_3()
{
    for(int i=0;i<1200040;i++) seg[i]=big;
    int temp,t1,t2;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='1') upd(1,1,n,i+1,0);
    }
    for(int i=0;i<q;i++)
    {
        if(vec[i].t==1)
        {
            t1=vec[i].u;
            t2=vec[i].v;
            temp=que(1,1,n,t1,t2-1);
            if(temp==big) printf("0\n");
            else printf("%d\n",(i+1)-temp);
        }
        else
        {
            t1=vec[i].u;
            upd(1,1,n,t1,i+1);
        }
    }
}

int main()
{
    bool ch=true;
    scanf("%d %d",&n,&q);
    scanf("%s",s);
    char tt[10];
    for(int i=0;i<q;i++)
    {
        scanf("%s",tt);
        if(tt[0]=='q')
        {
            scanf("%d %d",&x,&y);
            vec.push_back({1,x,y});
            if(y-x>1) ch=false;
        }
        else
        {
            scanf("%d",&x);
            vec.push_back({2,x,x});
        }
    }
    if(ch) solve_2();
    else solve_3();
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |     scanf("%s",s);
      |     ~~~~~^~~~~~~~
street_lamps.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%s",tt);
      |         ~~~~~^~~~~~~~~
street_lamps.cpp:108:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |             scanf("%d %d",&x,&y);
      |             ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:114:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~

Subtask #1
0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 6584 KB Output is correct
2 Correct 108 ms 6492 KB Output is correct
3 Correct 102 ms 6540 KB Output is correct
4 Correct 118 ms 7556 KB Output is correct
5 Correct 122 ms 6776 KB Output is correct
6 Correct 136 ms 7512 KB Output is correct
7 Correct 141 ms 6844 KB Output is correct
8 Correct 146 ms 6832 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 150 ms 13076 KB Output is correct
6 Correct 218 ms 13820 KB Output is correct
7 Correct 304 ms 14500 KB Output is correct
8 Correct 357 ms 16484 KB Output is correct
9 Correct 122 ms 11564 KB Output is correct
10 Correct 127 ms 12188 KB Output is correct
11 Correct 128 ms 12344 KB Output is correct
12 Correct 297 ms 15148 KB Output is correct
13 Correct 359 ms 16424 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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