oj.uz

Submission #163201

# Submission time Handle Problem Language Result Execution time Memory
163201 2019-11-11T18:05:30 Z TadijaSebez 즐거운 사진 수집 (JOI13_collecting) C++11
100 / 100
 1593 ms 70520 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=(1<<20);
const int L=21;
int n;
struct Solve1D
{
	int sum[L][N],state[N],cnt[L];
	Solve1D(){}
	void init()
	{
		for(int i=0;i<=n;i++) cnt[i]=1<<(n-i);
	}
	void Change(int x)
	{
		for(int i=0;i<=n;i++)
		{
			int sz=1<<i;
			int block=x/sz;
			if(sum[i][block]==0 || sum[i][block]==sz) cnt[i]--;
			if(state[x]==1) sum[i][block]--;
			else sum[i][block]++;
			if(sum[i][block]==0 || sum[i][block]==sz) cnt[i]++;
		}
		state[x]^=1;
	}
} R,C;
int main()
{
	int q;
	scanf("%i %i",&n,&q);
	ll sum=0;
	for(int i=0;i<=n;i++) sum+=(ll)(1<<i)*(1<<i);
	R.init();C.init();
	while(q--)
	{
		int t,x;
		scanf("%i %i",&t,&x);
		x--;
		if(t==0) R.Change(x);
		else C.Change(x);
		ll ans=sum;
		for(int i=1;i<=n;i++) ans-=(ll)4*R.cnt[i]*C.cnt[i];
		printf("%lld\n",ans);
	}
	return 0;
}

Compilation message

collecting.cpp: In function 'int main()':
collecting.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
collecting.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&t,&x);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 508 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 508 KB Output is correct
8 Correct 3 ms 508 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1547 ms 70476 KB Output is correct
2 Correct 1574 ms 70432 KB Output is correct
3 Correct 1424 ms 55096 KB Output is correct
4 Correct 1554 ms 70520 KB Output is correct
5 Correct 1551 ms 70248 KB Output is correct
6 Correct 1568 ms 68900 KB Output is correct
7 Correct 1593 ms 70260 KB Output is correct
8 Correct 1575 ms 70364 KB Output is correct
9 Correct 1513 ms 53716 KB Output is correct
10 Correct 1485 ms 56404 KB Output is correct
11 Correct 1579 ms 68844 KB Output is correct
12 Correct 1588 ms 68932 KB Output is correct
13 Correct 1474 ms 56108 KB Output is correct