結果

問題 No.1625 三角形の質問
コンテスト
ユーザー 沙耶花
提出日時 2021-07-23 22:28:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,176 bytes
コンパイル時間 4,404 ms
コンパイル使用メモリ 267,356 KB
最終ジャッジ日時 2025-01-23 08:14:32
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9 TLE * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:31:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   31 |         scanf("%d %d",&n,&q);
      |         ~~~~~^~~~~~~~~~~~~~~
main.cpp:37:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   37 |                 scanf("%lld %lld %lld %lld %lld %lld",&a[i],&b[i],&c[i],&d[i],&e[i],&f[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:48:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   48 |                         scanf("%lld %lld %lld %lld %lld %lld",&qa[i],&qb[i],&qc[i],&qd[i],&qe[i],&qf[i]);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:55:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   55 |                         scanf("%lld %lld",&qa[i],&qb[i]);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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 = 600;
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