oj.uz

Submission #1004971

# Submission time Handle Problem Language Result Execution time Memory
1004971 2024-06-22T05:21:21 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 27224 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)
    {
      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 + 1;
	  // 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]] << '\n';
	}
      // curtime++;
    }
}

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

Compilation message

street_lamps.cpp: In function 'void subtask2()':
street_lamps.cpp:48:7: warning: unused variable 't' [-Wunused-variable]
   48 |   int t[n] = {0};
      |       ^
street_lamps.cpp:50:7: warning: unused variable 'curtime' [-Wunused-variable]
   50 |   int curtime = 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 344 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 22772 KB Output is correct
2 Correct 190 ms 24312 KB Output is correct
3 Correct 1110 ms 24568 KB Output is correct
4 Execution timed out 5051 ms 27224 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
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 #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 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 344 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 150 ms 22772 KB Output is correct
9 Correct 190 ms 24312 KB Output is correct
10 Correct 1110 ms 24568 KB Output is correct
11 Execution timed out 5051 ms 27224 KB Time limit exceeded
12 Halted 0 ms 0 KB -