oj.uz

Submission #128745

# Submission time Handle Problem Language Result Execution time Memory
128745 2019-07-11T08:55:21 Z baluteshih Dragon 2 (JOI17_dragon2) C++14
60 / 100
 1719 ms 262148 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;

int bit[30005];
vector<pii> v[30005];

int Q(pii x)
{
	if(x.F<=0&&x.S<0) return 1;
	if(x.F>0&&x.S<=0) return 2;
	if(x.F>=0&&x.S>0) return 3;
	return 4;
}

bool yee(pii a,pii b)
{
	if(Q(a)!=Q(b)) return Q(a)<Q(b);
	return (ll)a.S*b.F<(ll)b.S*a.F;
}

bool yee2(pair<pii,pii> a,pair<pii,pii> b)
{
	return yee(a.F,b.F);
}

bool yee3(pii a,pii b)
{
	return !yee(a,b)&&!yee(b,a);
}

void modify(int x,int val,int t)
{ 
	for(;x<=v[t].size();x+=x&-x) bit[x]+=val;
}

int query(int x)
{
	int re=0;
	for(;x>0;x-=x&-x) re+=bit[x];
	return re;
}

struct mode
{
	int p,l,r,type;//count the number of l<=value<=r in [1,p]
	ll *i;
	//type 1:+ type -1:-
	bool operator<(const mode &a)const{
		return p<a.p;
	}
};

vector<pii> tb[30005];
vector<pair<pii,pii>> seq[30005],org[30005];
vector<int> pl[30005];
vector<mode> qs[30005];
pii operator-(const pii &a,const pii &b){return MP(a.F-b.F,a.S-b.S);}
pii angle(pii c,pii x){
	x=x-c;
	return x;
}
ll ans[100005],m;

void add_q(pii _l,pii _r,pii _x,pii _y,int p,int i)
{
	int l=lower_bound(ALL(seq[p]),MP(_l,MP(0,0)),yee2)-seq[p].begin();
	int r=upper_bound(ALL(seq[p]),MP(_r,MP(0,0)),yee2)-seq[p].begin();
	int x=lower_bound(ALL(v[p]),_x,yee)-v[p].begin();
	int y=upper_bound(ALL(v[p]),_y,yee)-v[p].begin();
	qs[p].pb(mode{r,x,y,1,&ans[i]}),qs[p].pb(mode{l,x,y,-1,&ans[i]});
}

void solve()
{
	for(int i=1;i<=m;++i)
	{
		sort(ALL(qs[i]));
		int nw=0;
		for(auto j:qs[i])
		{
			while(nw<j.p)
				++nw,modify(pl[i][nw-1],1,i);
			int sum=query(j.r)-query(j.l);
			*j.i+=j.type*sum;
		}
		for(int j=1;j<=nw;++j)
			modify(pl[i][j-1],-1,i);
		qs[i].clear();
	}
}

pii rg(pii x)
{
	return MP(-x.F,-x.S);
}

vector<pair<pii,pii>> interval(pii x)//x clockwise 180.
{
	if(Q(x)>=3) return vector<pair<pii,pii>>{MP(rg(x),x)};
	return vector<pair<pii,pii>>{MP(rg(x),MP(-1,0)),MP(MP(-1000000001,-1),x)};
}

int main()
{jizz
	int n,q,x,y,c;
	pii a,b,ag;
	cin >> n >> m;
	for(int i=0;i<n;++i)
		cin >> x >> y >> c,tb[c].pb(MP(x,y));
	cin >> a.F >> a.S >> b.F >> b.S >> q;
	if(a>b) swap(a,b);
	for(int i=1;i<=m;++i)
	{
		for(auto j:tb[i])
		{
			pii s=angle(a,j),t=angle(b,j);
			org[i].pb(MP(s,t)),v[i].pb(t);
		}
		seq[i]=org[i],sort(ALL(seq[i]),yee2);
		sort(ALL(v[i]),yee),v[i].resize(unique(ALL(v[i]),yee3)-v[i].begin());
		for(auto j:seq[i])
			pl[i].pb(upper_bound(ALL(v[i]),j.S,yee)-v[i].begin());
	}
	ag=angle(a,b);
	auto inter=interval(ag);
	for(int i=0;i<q;++i)
	{
		cin >> x >> y;
		//if(tb[x].size()>tb[y].size()) swap(x,y);
		for(int j=0;j<tb[x].size();++j)
		{
			int flag=0;
			for(auto k:inter)
				if((yee(k.F,org[x][j].F)||yee3(k.F,org[x][j].F))&&(yee(org[x][j].F,k.S)||yee3(org[x][j].F,k.S)))
					flag=1;
			vector<pair<pii,pii>> L,R;
			if(flag)
				L=interval(rg(org[x][j].F)),R=interval(org[x][j].S);
			else
				L=interval(org[x][j].F),R=interval(rg(org[x][j].S));
			for(auto l:L)
				for(auto r:R)
					add_q(l.F,l.S,r.F,r.S,y,i);
		}
	}
	solve();
	for(int i=0;i<q;++i)
		cout << ans[i] << "\n";
}
/*
4 2 
0 1 1
0 -1 1
1 2 2
-6 1 2
-2 0 2 0
2
1 2
2 1

3 2
-1000000000 -1 1
-999999998 -1 1
0 0 2
999999997 1 999999999 1
1
1 2

6 3
2 -1 1
1 0 1
0 3 2
2 4 2
5 4 3
3 9 3
0 0 3 3
6
1 2
1 3
2 1
2 3
3 1
3 2
*/

Compilation message

dragon2.cpp: In function 'void modify(int, int, int)':
dragon2.cpp:47:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(;x<=v[t].size();x+=x&-x) bit[x]+=val;
       ~^~~~~~~~~~~~~
dragon2.cpp: In function 'int main()':
dragon2.cpp:144:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<tb[x].size();++j)
               ~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5112 KB Output is correct
2 Correct 25 ms 6860 KB Output is correct
3 Correct 132 ms 23196 KB Output is correct
4 Correct 256 ms 48200 KB Output is correct
5 Correct 97 ms 18680 KB Output is correct
6 Correct 10 ms 5368 KB Output is correct
7 Correct 11 ms 5240 KB Output is correct
8 Correct 12 ms 5152 KB Output is correct
9 Correct 11 ms 5112 KB Output is correct
10 Correct 11 ms 5112 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7944 KB Output is correct
2 Correct 228 ms 23092 KB Output is correct
3 Correct 63 ms 10500 KB Output is correct
4 Correct 34 ms 7160 KB Output is correct
5 Correct 33 ms 8184 KB Output is correct
6 Correct 51 ms 8032 KB Output is correct
7 Correct 55 ms 8052 KB Output is correct
8 Correct 50 ms 8092 KB Output is correct
9 Correct 39 ms 8092 KB Output is correct
10 Correct 38 ms 7960 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5112 KB Output is correct
2 Correct 25 ms 6860 KB Output is correct
3 Correct 132 ms 23196 KB Output is correct
4 Correct 256 ms 48200 KB Output is correct
5 Correct 97 ms 18680 KB Output is correct
6 Correct 10 ms 5368 KB Output is correct
7 Correct 11 ms 5240 KB Output is correct
8 Correct 12 ms 5152 KB Output is correct
9 Correct 11 ms 5112 KB Output is correct
10 Correct 11 ms 5112 KB Output is correct
11 Correct 59 ms 7944 KB Output is correct
12 Correct 228 ms 23092 KB Output is correct
13 Correct 63 ms 10500 KB Output is correct
14 Correct 34 ms 7160 KB Output is correct
15 Correct 33 ms 8184 KB Output is correct
16 Correct 51 ms 8032 KB Output is correct
17 Correct 55 ms 8052 KB Output is correct
18 Correct 50 ms 8092 KB Output is correct
19 Correct 39 ms 8092 KB Output is correct
20 Correct 38 ms 7960 KB Output is correct
21 Correct 58 ms 7964 KB Output is correct
22 Correct 231 ms 22988 KB Output is correct
23 Correct 1719 ms 163868 KB Output is correct
24 Runtime error 1584 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -