oj.uz

답안 #432952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
432952 2021-06-18T15:33:36 Z TLP39 가로등 (APIO19_street_lamps) C++14
20 / 100
 152 ms 12664 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,x,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

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 6504 KB Output is correct
2 Correct 102 ms 9804 KB Output is correct
3 Correct 114 ms 10268 KB Output is correct
4 Correct 116 ms 12664 KB Output is correct
5 Correct 121 ms 11984 KB Output is correct
6 Correct 144 ms 12368 KB Output is correct
7 Correct 144 ms 12160 KB Output is correct
8 Correct 152 ms 12156 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 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

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