oj.uz

답안 #126866

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126866 2019-07-08T14:28:09 Z mahmoudbadawy Examination (JOI19_examination) C++17
0 / 100
 137 ms 45296 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops") 
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define F first
#define S second

using namespace std;
using namespace __gnu_pbds;

typedef tree<
pair<int,int>,
null_type,
less<pair<int,int> >,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int N=1e5+5;

static char stdinBuffer[1024];
static char* stdinDataEnd = stdinBuffer + sizeof (stdinBuffer);
static const char* stdinPos = stdinDataEnd;

void readAhead(size_t amount)
{
    size_t remaining = stdinDataEnd - stdinPos;
    if (remaining < amount) {
       memmove(stdinBuffer, stdinPos, remaining);
       size_t sz = fread(stdinBuffer + remaining, 1, sizeof (stdinBuffer) - remaining, stdin);
       stdinPos = stdinBuffer;
       stdinDataEnd = stdinBuffer + remaining + sz;
       if (stdinDataEnd != stdinBuffer + sizeof (stdinBuffer))
         *stdinDataEnd = 0;
    }
}

int read_int()
{
    readAhead(16);

    int x = 0;
    bool neg = false;
    if (*stdinPos == '-') {
       ++stdinPos;
       neg = true;
    }

    while (*stdinPos >= '0' && *stdinPos <= '9') {
       x *= 10;
       x += *stdinPos - '0';
       ++stdinPos;
    }

    return neg ? -x : x;
}

ordered_set btree[4*N];
pair<int,int> arr[N];
pair<pair<int,int>, pair<int,int> > qs[N];
vector<int> cmp;
int ans[N];
int n,q;

int get(int x)
{
	return lower_bound(cmp.begin(),cmp.end(),x)-cmp.begin();
}

void add(int ind,int sm,int x,int node=1,int l=0,int r=cmp.size()-1)
{
	if(r<ind||l>ind) return;
	btree[node].insert({sm,x});
	if(l==r)
		return;
	int mid=(l+r)/2;
	add(ind,sm,x,node<<1,l,mid);
	add(ind,sm,x,(node<<1)+1,mid+1,r);
}

void rem(int ind,int sm,int x,int node=1,int l=0,int r=cmp.size()-1)
{
	if(r<ind||l>ind) return;
	btree[node].erase({sm,x});
	if(l==r)
		return;
	int mid=(l+r)/2;
	rem(ind,sm,x,node<<1,l,mid);
	rem(ind,sm,x,(node<<1)+1,mid+1,r);
}

int query(int ql,int qr,int val,int node=1,int l=0,int r=cmp.size()-1)
{
	if(r<ql||qr<l) return 0;
	if(ql<=l&&r<=qr)
	{
		return btree[node].size()-btree[node].order_of_key({val,-1});
	}
	int mid=(l+r)/2;
	return query(ql,qr,val,node<<1,l,mid)+query(ql,qr,val,(node<<1)+1,mid+1,r);
}

int main()
{
	//scanf("%d %d",&n,&q);
	n=read_int(); q=read_int();
	for(int i=0;i<n;i++)
	{
		arr[i].F=read_int(); arr[i].S=read_int();
		//scanf("%d %d",&arr[i].F,&arr[i].S);
		cmp.push_back(arr[i].S);
	}
	for(int i=0;i<q;i++)
	{
		//scanf("%d %d %d",&qs[i].F.F,&qs[i].F.S,&qs[i].S.F);
		qs[i].F.F=read_int(); qs[i].F.S=read_int();
		qs[i].S.F=read_int();
		qs[i].S.S=i;
		cmp.push_back(qs[i].F.S);
	}
	sort(cmp.begin(),cmp.end());
	cmp.erase(unique(cmp.begin(),cmp.end()),cmp.end());
	sort(arr,arr+n);
	sort(qs,qs+q);
	for(int i=0;i<n;i++)
	{
		add(get(arr[i].S),arr[i].F+arr[i].S,i);
	}
	int curs=0;
	for(int i=0;i<q;i++)
	{
		while(arr[curs].F<qs[i].F.F)
		{
			rem(get(arr[curs].S),arr[curs].F+arr[curs].S,curs);
			curs++;
		}
		/*cout << "ON " << qs[i].F.F << " " << curs << endl;
		for(int i=0;i<btree[1].size();i++)
		{
			auto x=*btree[1].find_by_order(i);
			cout << x.F << " " << x.S << endl;
		}*/
		ans[qs[i].S.S]=query(get(qs[i].F.S),cmp.size()-1,qs[i].S.F);
	}
	for(int i=0;i<q;i++)
		printf("%d\n",ans[i]);
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 57.0

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