oj.uz

Submission #284853

# Submission time Handle Problem Language Result Execution time Memory
284853 2020-08-28T06:52:42 Z arnold518 Ruka (COI15_ruka) C++14
9 / 100
 2000 ms 2508 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int SQ = 800;

int N, M;
int X[MAXN+10], Y[MAXN+10];

struct Buc
{
	int off;
	vector<int> comp, val;
	Buc()
	{
		off=0;
		comp=val=vector<int>();
	}
};
	
int init(int p, int *A, Buc *B, int off)
{
	int l=max(1, p*SQ), r=min(N, p*SQ+SQ-1);
	int sum=0;
	B[p]=Buc(); B[p].off=off;
	vector<pii> V;
	for(int j=l; j<=r; j++)
	{
		if(A[j]==0) continue;
		int tl=sum, tr=sum+A[j];
		if(A[j]<0) tl--;
		else tl++;

		if(tl>tr) swap(tl, tr);
		tr++;
		V.push_back({tl, 1});
		V.push_back({tr, -1});
		B[p].comp.push_back(tl);
		B[p].comp.push_back(tr);
		sum+=A[j];
	}
	sort(B[p].comp.begin(), B[p].comp.end());
	B[p].comp.erase(unique(B[p].comp.begin(), B[p].comp.end()), B[p].comp.end());
	sort(V.begin(), V.end());
	B[p].val.resize(B[p].comp.size());
	int t=0;
	for(int i=0, j=0; i<B[p].comp.size(); i++)
	{
		for(; j<V.size() && V[j].first==B[p].comp[i]; j++) t+=V[j].second;
		B[p].val[i]=t;	
	}
	return sum;
}

void init(int *A, Buc *B)
{
	int sum=1;
	for(int i=0; i<=N/SQ; i++) sum+=init(i, A, B, sum);
}

int query(int p, Buc *B)
{
	int it=upper_bound(B[p].comp.begin(), B[p].comp.end(), -B[p].off)-B[p].comp.begin()-1;
	if(it<0) return 0;
	return B[p].val[it];
}

int query(Buc *B)
{
	int ans=0;
	for(int i=0; i<=N/SQ; i++) ans+=query(i, B);
	return ans;
}

void update(int p, int *A, Buc *B, int d)
{
	init(p/SQ, A, B, B[p/SQ].off);
	for(int i=p/SQ+1; i<=N/SQ; i++) B[i].off+=d;
}

Buc BX[MAXN/SQ+10], BY[MAXN/SQ+10];

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d%d", &X[i], &Y[i]);

	init(X, BX);
	init(Y, BY);

	scanf("%d", &M);
	int pos=1;
	while(M--)
	{
		char c;
		scanf(" %c", &c);
		if(c=='B') pos=max(1, pos-1);
		else if(c=='F') pos=min(N, pos+1);
		else if(c=='Q') printf("%d\n", query(BX)+query(BY));
		else
		{
			int nx, ny;
			scanf("%d%d", &nx, &ny);
			int dx=nx-X[pos], dy=ny-Y[pos];
			X[pos]=nx; Y[pos]=ny;
			update(pos, X, BX, dx);
			update(pos, Y, BY, dy);
		}
	}
}

Compilation message

ruka.cpp: In function 'int init(int, int*, Buc*, int)':
ruka.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0, j=0; i<B[p].comp.size(); i++)
      |                    ~^~~~~~~~~~~~~~~~~
ruka.cpp:53:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(; j<V.size() && V[j].first==B[p].comp[i]; j++) t+=V[j].second;
      |         ~^~~~~~~~~
ruka.cpp: In function 'int main()':
ruka.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
ruka.cpp:90:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |  for(int i=1; i<=N; i++) scanf("%d%d", &X[i], &Y[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |  scanf("%d", &M);
      |  ~~~~~^~~~~~~~~~
ruka.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |   scanf(" %c", &c);
      |   ~~~~~^~~~~~~~~~~
ruka.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |    scanf("%d%d", &nx, &ny);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 300 ms 384 KB Output is correct
4 Correct 225 ms 384 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 300 ms 384 KB Output is correct
4 Correct 225 ms 384 KB Output is correct
5 Execution timed out 2079 ms 2508 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 300 ms 384 KB Output is correct
4 Correct 225 ms 384 KB Output is correct
5 Execution timed out 2079 ms 2508 KB Time limit exceeded
6 Halted 0 ms 0 KB -