oj.uz

답안 #292447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
292447 2020-09-07T01:52:09 Z arnold518 Examination (JOI19_examination) C++14
0 / 100
 170 ms 20476 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 = 2e5;

struct Data
{
	int x, y, p, s;
};

int N, Q;
vector<Data> V;
vector<int> comp;
int ans[MAXN+10];

int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1; }

int tree[MAXN+10];

void myassert(bool x)
{
	if(!x) while(1);
}

void update(int i, int k)
{
	myassert(1<=i && i<=N+Q);
	for(i=N+Q-i+1; i<=N+Q; i+=(i&-i)) tree[i]+=k;
}

int query(int i)
{
	myassert(1<=i && i<=N+Q);
	int ret=0;
	for(i=N+Q-i+1; i>0; i-=(i&-i)) ret+=tree[i];
	return ret;
}

int flush(int i)
{
	myassert(1<=i && i<=N+Q);
	for(i=N+Q-i+1; i<=N+Q; i+=(i&-i)) tree[i]=0;
}

void solve(int l, int r)
{
	if(l>=r) return;
	int mid=l+r>>1;

	vector<Data> L, R;
	for(int i=l; i<=mid; i++) if(V[i].p==0) L.push_back(V[i]);
	for(int i=mid+1; i<=r; i++) if(V[i].p) R.push_back(V[i]);

	sort(L.begin(), L.end(), [&](const Data &p, const Data &q) { return p.x>q.x; });
	sort(R.begin(), R.end(), [&](const Data &p, const Data &q) { return p.x>q.x; });

	for(int i=0, j=0; i<R.size(); i++)
	{
		for(; j<L.size() && L[j].x>=R[i].x; j++)
		{
			update(getcomp(L[j].y), 1);
		}
		ans[R[i].p]+=query(getcomp(R[i].y));
	}
	for(int j=0; j<L.size(); j++) flush(getcomp(L[j].y));

	return;
	solve(l, mid);
	solve(mid+1, r);
}

int main()
{
	scanf("%d%d", &N, &Q);
	for(int i=1; i<=N; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		V.push_back({x, y, 0, x+y});
		comp.push_back(y);
	}
	for(int i=1; i<=Q; i++)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		V.push_back({x, y, i, z});
		comp.push_back(y);
	}

	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());

	sort(V.begin(), V.end(), [&](const Data &p, const Data &q)
	{
		if(p.s!=q.s) return p.s>q.s;
		return p.p<q.p;
	});

	solve(0, V.size()-1);
	for(int i=1; i<=Q; i++) printf("%d\n", ans[i]);
}

Compilation message

examination.cpp: In function 'int flush(int)':
examination.cpp:47:1: warning: no return statement in function returning non-void [-Wreturn-type]
   47 | }
      | ^
examination.cpp: In function 'void solve(int, int)':
examination.cpp:52:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |  int mid=l+r>>1;
      |          ~^~
examination.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=0, j=0; i<R.size(); i++)
      |                    ~^~~~~~~~~
examination.cpp:63:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(; j<L.size() && L[j].x>=R[i].x; j++)
      |         ~^~~~~~~~~
examination.cpp:69:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int j=0; j<L.size(); j++) flush(getcomp(L[j].y));
      |               ~^~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |   scanf("%d%d%d", &x, &y, &z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 170 ms 20476 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 170 ms 20476 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -