oj.uz

Submission #128734

# Submission time Handle Problem Language Result Execution time Memory
128734 2019-07-11T08:47:55 Z baluteshih Dragon 2 (JOI17_dragon2) C++14
60 / 100
 1725 ms 262144 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)
{
	//cout << "modify " << x << " " << val << "\n";
	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)
{
	//cout << "add_q " << p << " " << i << " -> (" << _l.F << "," << _l.S << ") (" << _r.F << "," << _r.S << "): (" << _x.F << "," << _x.S << ") (" << _y.F << "," << _y.S << ")\n";
	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();
	//cout << l << " " << r << " " << x << " " << y << "\n";
	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)
	{
		//cout << "solve " << i << "\n";
		sort(ALL(qs[i]));
		int nw=0;
		/*cout << "???\n";
		for(auto j:qs[i])
			cout << j.p << " [" << j.l << "," << j.r << "] " << j.type << "\n";
		cout << "ed\n";*/
		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);
			//cout << j.i-ans << " += " << j.type*sum << "\n";
			*j.i+=j.type*sum;
		}
		//cout << "yee\n";
		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);
		//cout << i << ": ";
		//for(auto j:seq[i])
		//	cout << "(" << j.F << "," << j.S << ") ";
		//ET;
		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());
		//for(int j:pl[i])
		//	cout << j << " ";
		//ET;
	}
	ag=angle(a,b);
	auto inter=interval(ag);
	for(int i=0;i<q;++i)
	{
		cin >> 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:48: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:160: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 5188 KB Output is correct
2 Correct 25 ms 6840 KB Output is correct
3 Correct 132 ms 23196 KB Output is correct
4 Correct 256 ms 48760 KB Output is correct
5 Correct 100 ms 19448 KB Output is correct
6 Correct 10 ms 5240 KB Output is correct
7 Correct 10 ms 5368 KB Output is correct
8 Correct 10 ms 5180 KB Output is correct
9 Correct 9 ms 5112 KB Output is correct
10 Correct 9 ms 5112 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 8732 KB Output is correct
2 Correct 228 ms 23620 KB Output is correct
3 Correct 64 ms 11128 KB Output is correct
4 Correct 34 ms 7672 KB Output is correct
5 Correct 34 ms 8700 KB Output is correct
6 Correct 51 ms 8608 KB Output is correct
7 Correct 53 ms 8576 KB Output is correct
8 Correct 50 ms 8476 KB Output is correct
9 Correct 39 ms 8348 KB Output is correct
10 Correct 39 ms 8348 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5188 KB Output is correct
2 Correct 25 ms 6840 KB Output is correct
3 Correct 132 ms 23196 KB Output is correct
4 Correct 256 ms 48760 KB Output is correct
5 Correct 100 ms 19448 KB Output is correct
6 Correct 10 ms 5240 KB Output is correct
7 Correct 10 ms 5368 KB Output is correct
8 Correct 10 ms 5180 KB Output is correct
9 Correct 9 ms 5112 KB Output is correct
10 Correct 9 ms 5112 KB Output is correct
11 Correct 57 ms 8732 KB Output is correct
12 Correct 228 ms 23620 KB Output is correct
13 Correct 64 ms 11128 KB Output is correct
14 Correct 34 ms 7672 KB Output is correct
15 Correct 34 ms 8700 KB Output is correct
16 Correct 51 ms 8608 KB Output is correct
17 Correct 53 ms 8576 KB Output is correct
18 Correct 50 ms 8476 KB Output is correct
19 Correct 39 ms 8348 KB Output is correct
20 Correct 39 ms 8348 KB Output is correct
21 Correct 57 ms 8476 KB Output is correct
22 Correct 229 ms 23496 KB Output is correct
23 Correct 1725 ms 164408 KB Output is correct
24 Runtime error 1599 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -