제출 #292450

#제출 시각아이디문제언어결과실행 시간메모리
292450arnold518Examination (JOI19_examination)C++14
100 / 100
641 ms13788 KiB
#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;
 
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 update(int i, int k) { for(i=N-i+1; i<=N; i+=(i&-i)) tree[i]+=k; }
int query(int i) { int ret=0; for(i=N-i+1; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
void flush(int i) { for(i=N-i+1; i<=N; i+=(i&-i)) tree[i]=0; }
 
void solve(int l, int r)
{
	if(l==r) return;
	int mid=l+r>>1;
	solve(l, mid);
	solve(mid+1, r);
	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));
}
 
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});
	}
 
	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]);
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'void solve(int, int)':
examination.cpp:30:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |  int mid=l+r>>1;
      |          ~^~
examination.cpp:40:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0, j=0; i<R.size(); i++)
      |                    ~^~~~~~~~~
examination.cpp:42:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(; j<L.size() && L[j].x>=R[i].x; j++)
      |         ~^~~~~~~~~
examination.cpp:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int j=0; j<L.size(); j++) flush(getcomp(L[j].y));
      |               ~^~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   scanf("%d%d%d", &x, &y, &z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...