oj.uz

답안 #292449

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
292449 2020-09-07T02:08:59 Z arnold518 Examination (JOI19_examination) C++14
20 / 100
 168 ms 12772 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));
	}
	return;
	for(int j=0; j<L.size(); j++) flush(getcomp(L[j].y));

	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:70:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  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 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 10440 KB Output is correct
2 Correct 168 ms 12772 KB Output is correct
3 Correct 165 ms 12644 KB Output is correct
4 Correct 113 ms 11612 KB Output is correct
5 Correct 141 ms 12028 KB Output is correct
6 Correct 93 ms 10972 KB Output is correct
7 Correct 164 ms 12508 KB Output is correct
8 Correct 163 ms 12588 KB Output is correct
9 Correct 155 ms 12380 KB Output is correct
10 Correct 131 ms 11976 KB Output is correct
11 Correct 103 ms 11612 KB Output is correct
12 Correct 83 ms 10852 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 10440 KB Output is correct
2 Correct 168 ms 12772 KB Output is correct
3 Correct 165 ms 12644 KB Output is correct
4 Correct 113 ms 11612 KB Output is correct
5 Correct 141 ms 12028 KB Output is correct
6 Correct 93 ms 10972 KB Output is correct
7 Correct 164 ms 12508 KB Output is correct
8 Correct 163 ms 12588 KB Output is correct
9 Correct 155 ms 12380 KB Output is correct
10 Correct 131 ms 11976 KB Output is correct
11 Correct 103 ms 11612 KB Output is correct
12 Correct 83 ms 10852 KB Output is correct
13 Incorrect 151 ms 10848 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -