oj.uz

Submission #284847

# Submission time Handle Problem Language Result Execution time Memory
284847 2020-08-28T06:49:03 Z arnold518 Ruka (COI15_ruka) C++14
9 / 100
 2000 ms 4344 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 = 400;

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

struct Buc
{
	ll off;
	vector<ll> comp, val;
	Buc()
	{
		off=0;
		comp=val=vector<ll>();
	}
};
	
ll init(int p, ll *A, Buc *B, ll off)
{
	int l=max(1, p*SQ), r=min(N, p*SQ+SQ-1);
	ll sum=0;
	B[p]=Buc(); B[p].off=off;
	vector<pll> V;
	for(int j=l; j<=r; j++)
	{
		if(A[j]==0) continue;
		ll 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());
	ll 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(ll *A, Buc *B)
{
	ll 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, ll *A, Buc *B, ll d)
{
	ll sum=B[p/SQ].off;
	sum+=init(p/SQ, A, B, sum);
	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("%lld%lld", &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
		{
			ll nx, ny;
			scanf("%lld%lld", &nx, &ny);
			ll 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 'll init(int, ll*, Buc*, ll)':
ruka.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long 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<long long int, long long 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:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
ruka.cpp:91:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |  for(int i=1; i<=N; i++) scanf("%lld%lld", &X[i], &Y[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |  scanf("%d", &M);
      |  ~~~~~^~~~~~~~~~
ruka.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |   scanf(" %c", &c);
      |   ~~~~~^~~~~~~~~~~
ruka.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |    scanf("%lld%lld", &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 5 ms 512 KB Output is correct
3 Correct 139 ms 512 KB Output is correct
4 Correct 97 ms 504 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 5 ms 512 KB Output is correct
3 Correct 139 ms 512 KB Output is correct
4 Correct 97 ms 504 KB Output is correct
5 Execution timed out 2090 ms 4344 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 5 ms 512 KB Output is correct
3 Correct 139 ms 512 KB Output is correct
4 Correct 97 ms 504 KB Output is correct
5 Execution timed out 2090 ms 4344 KB Time limit exceeded
6 Halted 0 ms 0 KB -