oj.uz

Submission #1004974

# Submission time Handle Problem Language Result Execution time Memory
1004974 2024-06-22T05:26:18 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 188 ms 27996 KB 
#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};

  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';
	}
    }
}

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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 21240 KB Output is correct
2 Correct 122 ms 21580 KB Output is correct
3 Correct 131 ms 22000 KB Output is correct
4 Correct 159 ms 21920 KB Output is correct
5 Correct 168 ms 26776 KB Output is correct
6 Correct 169 ms 26964 KB Output is correct
7 Correct 183 ms 27996 KB Output is correct
8 Correct 188 ms 27616 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 121 ms 21240 KB Output is correct
9 Correct 122 ms 21580 KB Output is correct
10 Correct 131 ms 22000 KB Output is correct
11 Correct 159 ms 21920 KB Output is correct
12 Correct 168 ms 26776 KB Output is correct
13 Correct 169 ms 26964 KB Output is correct
14 Correct 183 ms 27996 KB Output is correct
15 Correct 188 ms 27616 KB Output is correct
16 Incorrect 1 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -