Submission #1004966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004966		vjudge1	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	116 ms	21668 KiB

street_lamps

#include<bits/stdc++.h>

using namespace std;

#define toggle 1
#define query 2

int n, q;
string s;
vector<vector<int> > Q;

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};
  fill(t, t + n, 1);

  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;
	  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]] + 1;
	  cout << cnt[qy[1]] + ext << '\n';
	}
    }
}

int main()
{
  cin >> n >> q;
  cin >> s;
  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--;
	  Q.push_back({query, a, b});
	}
    }
  // if(max(n, q) <= 100)
  // subtask1();
  // else
  subtask2();
  return 0;
}

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