oj.uz

답안 #1004953

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1004953 2024-06-22T05:00:04 Z vjudge1 가로등 (APIO19_street_lamps) C++17
20 / 100
 116 ms 21596 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++;
      
      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
	{
	  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
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 116 ms 21596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 Incorrect 116 ms 21596 KB Output isn't correct
9 Halted 0 ms 0 KB -