Submission #1005218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005218		vjudge1	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	200 ms	22916 KiB

street_lamps

#include<bits/stdc++.h>

using namespace std;

#define toggle 1
#define query 2

const int N = 1e5 +5 , k = 20;
int sp[N][k];
int n, q;
string s;
vector<vector<int> > Q;

int getmax(int l, int r)
{
  int b = 31 - __builtin_clz(r - l);
  return max(sp[l][b], sp[r - (1 << b)][b]);
}

void subtask1()
{
  int cnt[n + 1][n + 1];
  memset(cnt, 0, sizeof(cnt));
  
  int pref[n + 1];
  pref[0] = 0;
  for(int i = 0; i < n; i ++)
    pref[i + 1] = pref[i] + s[i] - '0';

  
  
  for(auto qy : Q)
    {
      for(int i = 0; i <= n; i ++)
	for(int j = i + 1; j <= n; j ++)
	  if(pref[j] - pref[i] == j - i)
	    cnt[i][j]++;
      
      if(qy[0] == toggle)
	{
	  s[qy[1]] = '1' + '0' - s[qy[1]];
	  
	  pref[0] = 0;
	  for(int i = 0; i < n; i ++)
	    pref[i + 1] = pref[i] + s[i] - '0';
	}
      
      if(qy[0] == query)
	cout << cnt[qy[1]][qy[2]] << '\n';
    }
}

void subtask2() // b - a == 1
{
  int cnt[n] = {0};
  int t[n] = {0};

  int curtime = 0;
  for(auto qy : Q)
    {
      curtime++;
      // for(int i = 0; i < n; i ++)
      // cnt[i] += s[i] - '0';
      
      if(qy[0] == toggle)
	{
	  s[qy[1]] = '1' + '0' - s[qy[1]];

	  if(s[qy[1]] == '1')
	    t[qy[1]] = curtime;
	  else
	    cnt[qy[1]] += curtime - t[qy[1]]; 
	}
      else
	{
	  // cerr << s << endl;
	  int ext = 0;
	  if(s[qy[1]] == '1')
	    ext = curtime - t[qy[1]];
	  cout << cnt[qy[1]] + ext << '\n';
	}
    }
}

void subtask3()
{
   int t[n] = {0};
   fill(t, t + n, Q.size() + 10);

  int curtime = 0;
  for(auto qy : Q)
    {
      curtime++;
      if(qy[0] == toggle)
	{
	  s[qy[1]] = '1' + '0' - s[qy[1]];
	  if(s[qy[1]] == '1')
	    t[qy[1]] = curtime;
	}
    }

  int k = 20;
  for(int i = n - 1; i >= 0; i--)
    {
      sp[i][0] = t[i];
      for(int l = 1; i + (1 << l) <= n; l++)
	sp[i][l] = max(sp[i][l - 1], sp[i + 1<<(l-1)][l-1]);
    }
  
  curtime = 0;
  for(auto qy : Q)
    {
      curtime++;
      if(qy[0] == query)
	{
	  cout << max(0, curtime - getmax(qy[1], qy[2]));
	}

      
    }

  
}

int main()
{
  cin >> n >> q;
  cin >> s;
  bool s2 = true;
  for(int i = 0; i < q; i ++)
    {
      string cmd;
      cin >> cmd;
      if(cmd == "toggle")
	{
	  int x;
	  cin >> x;
	  x--;
	  Q.push_back({toggle, x});
	}
      else
	{
	  int a, b;
	  cin >> a >> b;
	  a--, b--;
	  if(b - a != 1) s2 = false;
	  Q.push_back({query, a, b});
	}
    }
  if(max(n, q) <= 100)
    subtask1();
  else if(s2)
    subtask2();
  else
    subtask3();
  return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void subtask3()':
street_lamps.cpp:107:36: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  107 |  sp[i][l] = max(sp[i][l - 1], sp[i + 1<<(l-1)][l-1]);
      |                                  ~~^~~
street_lamps.cpp:102:7: warning: unused variable 'k' [-Wunused-variable]
  102 |   int k = 20;
      |       ^

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