Submission #432844

#	Time	Username	Problem	Language	Result	Execution time	Memory
432844		Amylopectin	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	405 ms	31116 KiB

street_lamps

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
const int mxn = 800010,mxi = 1e9 + 10;
char s[mxn] = {},inp[mxn] = {};
struct we
{
    int tim,sta;
};
vector<struct we> li[mxn] = {};
//struct we li[mxn][mxn] = {};
int coun[mxn] = {},cva[mxn] = {},se[mxn] = {};
int fima(int l,int r)
{
    if(l > r)
        return l;
    return r;
}
int cre(int cl,int cr,int no)
{
    if(cl == cr)
    {
        se[no] = mxi;
        return 0;
    }
    int mid = (cl + cr) / 2;
    cre(cl,mid,no*2);
    cre(mid+1,cr,no*2+1);
    se[no] = mxi;
    return 0;
}
int ins(int cl,int cr,int no,int tn,int iva)
{
    if(cr < tn || cl > tn)
    {
//        se[no] = iva;
        return 0;
    }
    if(cl == cr)
    {
        se[no] = iva;
        return 0;
    }
    int mid = (cl + cr) / 2;
    ins(cl,mid,no*2,tn,iva);
    ins(mid+1,cr,no*2+1,tn,iva);
    se[no] = fima(se[no*2],se[no*2+1]);
    return 0;
}
int firma(int cl,int cr,int no,int tl,int tr)
{
    if(cr < tl || cl > tr)
    {
        return 0;
    }
    if(cl >= tl && cr <= tr)
    {
        return se[no];
    }
    int mid = (cl + cr) / 2,cma = 0;
    cma = fima(cma,firma(cl,mid,no*2,tl,tr));
    cma = fima(cma,firma(mid+1,cr,no*2+1,tl,tr));
//    se[no] = fima(se[no*2],se[no*2+1]);
    return cma;
}
int main()
{
    int i,j,n,m,q,f,t,cst,cou,su,k;
    scanf("%d %d %s",&n,&q,&s);
    cre(0,n-1,1);
    for(i=0; i<n; i++)
    {
//        li[i][0] = {0,s[i] - '0'};
//        li[i].push_back({0,s[i] - '0'});
        if(s[i] == '1')
        {
            ins(0,n-1,1,i,0);
        }
//        coun[i] = 1;
    }
    for(i=1; i<=q; i++)
    {
        scanf("%s",&inp);
        if(inp[0] == 't')
        {
            scanf("%d",&f);
            f --;
            ins(0,n-1,1,f,i);
//            if(li[f][li[f].size()-1].sta == 1)
//            {
//                cva[f] += i - li[f][li[f].size()-1].tim;
//            }
//            li[f].push_back({i,(li[f][li[f].size()-1].sta + 1) % 2});
//            li[f][coun[f]] = {i,(li[f][coun[f]-1].sta + 1) % 2};
//            coun[f] ++;
        }
        else
        {
            scanf("%d %d",&f,&t);
            f --;
            t --;
            su = firma(0,n-1,1,f,t-1);
            if(su == mxi)
            {
                su = 0;
            }
            else
            {
                su = i-su;
            }
//            su = cva[f];
//            if(li[f][li[f].size()-1].sta == 1)
//            {
//                su += i - li[f][li[f].size()-1].tim;
//            }
//            for(j=1; j<=i; j++)
//            {
//                cva[j] = 1;
//            }
//            for(j=f; j<t; j++)
//            {
//                cst = li[j][0].sta;
//                cou = 1;
////                cva[0] &= cst;
//                for(k=1; k<=i; k++)
//                {
//                    cva[k] &= cst;
//                    if(cou < coun[j] && li[j][cou].tim == k)
//                    {
//                        cst = (cst+1) % 2;
//                        cou ++;
//                    }
//                }
//            }
//            su = 0;
//            for(k=1; k<=i; k++)
//            {
//                su += cva[k];
//            }
            printf("%d\n",su);
        }
    }
    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:70:19: warning: format '%s' expects argument of type 'char*', but argument 4 has type 'char (*)[800010]' [-Wformat=]
   70 |     scanf("%d %d %s",&n,&q,&s);
      |                  ~^        ~~
      |                   |        |
      |                   char*    char (*)[800010]
street_lamps.cpp:84:17: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[800010]' [-Wformat=]
   84 |         scanf("%s",&inp);
      |                ~^  ~~~~
      |                 |  |
      |                 |  char (*)[800010]
      |                 char*
street_lamps.cpp:69:11: warning: unused variable 'j' [-Wunused-variable]
   69 |     int i,j,n,m,q,f,t,cst,cou,su,k;
      |           ^
street_lamps.cpp:69:15: warning: unused variable 'm' [-Wunused-variable]
   69 |     int i,j,n,m,q,f,t,cst,cou,su,k;
      |               ^
street_lamps.cpp:69:23: warning: unused variable 'cst' [-Wunused-variable]
   69 |     int i,j,n,m,q,f,t,cst,cou,su,k;
      |                       ^~~
street_lamps.cpp:69:27: warning: unused variable 'cou' [-Wunused-variable]
   69 |     int i,j,n,m,q,f,t,cst,cou,su,k;
      |                           ^~~
street_lamps.cpp:69:34: warning: unused variable 'k' [-Wunused-variable]
   69 |     int i,j,n,m,q,f,t,cst,cou,su,k;
      |                                  ^
street_lamps.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d %d %s",&n,&q,&s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf("%s",&inp);
      |         ~~~~~^~~~~~~~~~~
street_lamps.cpp:87:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |             scanf("%d",&f);
      |             ~~~~~^~~~~~~~~
street_lamps.cpp:100:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |             scanf("%d %d",&f,&t);
      |             ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20