Submission #241339

#	Time	Username	Problem	Language	Result	Execution time	Memory
241339		arnold518	단층 (JOI16_ho_t5)	C++14	100 / 100	163 ms	15480 KiB

2016_ho_t5

#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 2e5;

struct Data
{
	ll X, D, L;
};

int N, Q, S;
Data A[MAXN+10];

struct BIT
{
	ll tree[MAXN+10];
	void init() { memset(tree, 0, sizeof(tree)); }
	void update(int i, ll k) { for(i=max(i, 1); i<=N; i+=(i&-i)) tree[i]+=k; }
	ll query(int i) { ll ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
}bitx, bity;

int main()
{
	int i, j;

	scanf("%d%d", &N, &Q);
	for(i=1; i<=Q; i++) scanf("%lld%lld%lld", &A[i].X, &A[i].D, &A[i].L);
	reverse(A+1, A+Q+1);
		
	bitx.init(); bity.init();
	bity.update(1, N);
	for(i=2; i<=N; i++) bity.update(i, -1);
	for(i=1; i<=N; i++) bitx.update(i, 1);
	for(i=1; i<=Q; i++)
	{
		if(A[i].D==1)
		{
			int lo=0, hi=N+1;
			while(lo+1<hi)
			{
				int mid=lo+hi>>1;
				if(bitx.query(mid)<=A[i].X) lo=mid;
				else hi=mid;
			}
			bity.update(N-lo+1, -2*A[i].L);
		}
		else
		{
			int lo=0, hi=N+1;
			while(lo+1<hi)
			{
				int mid=lo+hi>>1;
				if(bity.query(N-mid+1)>A[i].X) hi=mid;
				else lo=mid;
			}
			bitx.update(hi, 2*A[i].L);
		}
		//for(j=1; j<=N; j++) printf("(%lld %lld) ", bitx.query(j), bity.query(N-j+1)); printf("\n");	
	}
	for(i=1; i<=N; i++) printf("%lld\n", (bitx.query(i)-bity.query(N-i+1))/2);
}

Compilation message (stderr)

2016_ho_t5.cpp: In function 'int main()':
2016_ho_t5.cpp:45:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=lo+hi>>1;
             ~~^~~
2016_ho_t5.cpp:56:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=lo+hi>>1;
             ~~^~~
2016_ho_t5.cpp:28:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
2016_ho_t5.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
2016_ho_t5.cpp:31:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=Q; i++) scanf("%lld%lld%lld", &A[i].X, &A[i].D, &A[i].L);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 16 / 16
• Subtask 3: 66 / 66