結果

問題 No.1625 三角形の質問
ユーザー 沙耶花沙耶花
提出日時 2021-07-23 22:30:23
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2,854 ms / 6,000 ms
コード長 3,177 bytes
コンパイル時間 5,667 ms
コンパイル使用メモリ 274,196 KB
実行使用メモリ 55,776 KB
最終ジャッジ日時 2023-09-25 22:43:27
合計ジャッジ時間 38,698 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,356 KB
testcase_01 AC 49 ms
7,756 KB
testcase_02 AC 772 ms
27,128 KB
testcase_03 AC 227 ms
25,712 KB
testcase_04 AC 413 ms
21,984 KB
testcase_05 AC 937 ms
35,248 KB
testcase_06 AC 2,854 ms
55,324 KB
testcase_07 AC 2,722 ms
55,076 KB
testcase_08 AC 2,558 ms
55,188 KB
testcase_09 AC 2,458 ms
55,196 KB
testcase_10 AC 2,520 ms
55,356 KB
testcase_11 AC 2,580 ms
55,068 KB
testcase_12 AC 2,402 ms
55,776 KB
testcase_13 AC 2,286 ms
55,076 KB
testcase_14 AC 2,264 ms
55,304 KB
testcase_15 AC 2,407 ms
55,064 KB
testcase_16 AC 501 ms
31,068 KB
testcase_17 AC 730 ms
35,496 KB
testcase_18 AC 566 ms
38,212 KB
testcase_19 AC 910 ms
40,152 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000001
int sz = 3000;
long long get(long long a,long long b,long long c,long long d,long long e,long long f){
	c -= a;
	d -= b;
	e -= a;
	f -= b;
	
	long long ret = abs(e*d - f*c);
	return ret;
}

long long op(long long a,long long b){
	return max(a,b);
}

long long ee(){
	return 0LL;
}

int main(){
	
	int n,q;
	scanf("%d %d",&n,&q);
	
	vector<long long> a(n),b(n),c(n),d(n),e(n),f(n);
	vector<long long> v(n),qv(q);
	vector<long long> t;
	rep(i,n){
		scanf("%lld %lld %lld %lld %lld %lld",&a[i],&b[i],&c[i],&d[i],&e[i],&f[i]);
		t.push_back(min({a[i],c[i],e[i]}));
		t.push_back(max({a[i],c[i],e[i]})+1);
		v[i] = get(a[i],b[i],c[i],d[i],e[i],f[i]);
	}
	
	vector<long long> type(q),qa(q),qb(q),qc(q),qd(q),qe(q),qf(q);

	rep(i,q){
		cin>>type[i];
		if(type[i]==1){
			scanf("%lld %lld %lld %lld %lld %lld",&qa[i],&qb[i],&qc[i],&qd[i],&qe[i],&qf[i]);
			t.push_back(min({qa[i],qc[i],qe[i]}));
			t.push_back(max({qa[i],qc[i],qe[i]})+1);
			qv[i] = get(qa[i],qb[i],qc[i],qd[i],qe[i],qf[i]);
			//cout<<qv[i]<<endl;
		}
		else{
			scanf("%lld %lld",&qa[i],&qb[i]);
			t.push_back(qa[i]);
			t.push_back(qb[i]+1);
		}
	}
	sort(t.begin(),t.end());
	t.erase(unique(t.begin(),t.end()),t.end());
	
	vector<int> l(n),r(n);
	
	rep(i,n){
		l[i] = distance(t.begin(),lower_bound(t.begin(),t.end(),min({a[i],c[i],e[i]})));
		r[i] = distance(t.begin(),lower_bound(t.begin(),t.end(),1+max({a[i],c[i],e[i]})));
	}
	vector<int> lq(q),rq(q);
	rep(i,q){
		if(type[i]==1){
			lq[i] = distance(t.begin(),lower_bound(t.begin(),t.end(),min({qa[i],qc[i],qe[i]})));
			rq[i] = distance(t.begin(),lower_bound(t.begin(),t.end(),1+max({qa[i],qc[i],qe[i]})));
		}
		else{
			lq[i] = distance(t.begin(),lower_bound(t.begin(),t.end(),qa[i]));
			rq[i] = distance(t.begin(),lower_bound(t.begin(),t.end(),qb[i]+1));
		}
	}
	
	vector<long long> ans(q,0LL);
	
	for(int i=0;i<q;i+=sz){
		//cout<<i<<endl;
		segtree<long long,op,ee> seg(t.size());
		vector<vector<pair<int,long long>>> Add(t.size());
		rep(j,n){
			Add[r[j]].emplace_back(l[j],v[j]);
		}
		rep(j,i){
			if(type[j]==1){
				Add[rq[j]].emplace_back(lq[j],qv[j]);
			}
		}
		//cout<<i<<endl;
		vector<vector<pair<int,long long>>> Check(t.size());
		//cout<<i<<endl;
		for(int j=i;j<min(q,i+sz);j++){
			if(type[j]==2){
				Check[rq[j]].emplace_back(lq[j],j);
			}
		}
		rep(j,t.size()){
			rep(k,Add[j].size()){
				int pos = Add[j][k].first;
				long long vv = Add[j][k].second;
				seg.set(pos,max(seg.get(pos),vv));
			}
			
			rep(k,Check[j].size()){
				int pos = Check[j][k].first;
				long long vv = Check[j][k].second;
				ans[vv] = max(ans[vv],seg.prod(pos,t.size()));
			}
		}
		//cout<<i<<endl;
		for(int j=i;j<min(q,i+sz);j++){
			if(type[j]==2){
				for(int k=i;k<j;k++){
					if(type[k]==1){
						if(lq[k]>=lq[j]&&rq[k]<=rq[j]){
							ans[j] = max(ans[j],qv[k]);
						}
					}
					
				}
			}
		}
		
	}
	
	rep(i,q){
		if(type[i]==1)continue;
		long long P = ans[i];
		if(P==0)P = -1;
		printf("%lld\n",P);
	}
	
	return 0;
}
0