提出 #41815780

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

#define de(x) cout<<#x<<"="<<x<<endl

using ll = long long;

const int N = 3e5+5;

ll n,h;
ll t[N],d[N];
vector<ll> tt;
vector<ll> g[N];
map<ll,int> mp;

bool check(ll mid){
	vector<pair<ll,ll> > vc;
	for (int i=0; i<n; i++){
		vc.push_back({d[i]*t[i],t[i]});
	}
	sort(vc.rbegin(),vc.rend());
	ll lst=mid;
	ll dam=0;
	ll mx=0;
	int top=0;
	for (int i=0; i<tt.size(); i++){
		if (tt[i]>mid){
			for (auto u : g[i]){
				mx=max(mx,d[u]);
			}
			while (top<vc.size() && vc[top].second>=tt[i]){
				top++;
			}
			continue;
		}
		ll cur=(top==vc.size()?0:vc[top].first);
		if (cur!=0 && 2000000000000000000ll/cur<(lst-tt[i]+1)){
			return 1;
		}
		if (mx!=0 && 4000000000000000000ll/mx<(lst+tt[i])*(lst-tt[i]+1)){
			return 1;
		}
		ll a1=cur*(lst-tt[i]+1);
		ll a2=mx*(lst+tt[i])*(lst-tt[i]+1)/2;
		dam+=max(a1,a2);
		dam=min(dam,2000000000000000000ll);
		lst=tt[i]-1;
		for (auto u : g[i]){
			mx=max(mx,d[u]);
		}
		while (top<vc.size() && vc[top].second>=tt[i]){
			top++;
		}
	}
//	cout<<mid<<":"<<dam<<endl;
	return dam>=h;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>h;
	for (int i=0; i<n; i++){
		cin>>t[i]>>d[i];
		tt.push_back(t[i]);
	}
	tt.push_back(1);
	sort(tt.begin(),tt.end());
	tt.erase(unique(tt.begin(),tt.end()),tt.end());
	reverse(tt.begin(),tt.end());
	for (int i=0; i<tt.size(); i++){
		mp[tt[i]]=i;
	}
	for (int i=0; i<n; i++){
		g[mp[t[i]]].push_back(i);
	}
	ll l=0,r=2e18;
	while (l+1<r){
		ll mid=(l+r)/2;
	//	cout<<mid<<endl;
		if (check(mid)){
			r=mid;
		}
		else{
			l=mid;
		}
	}
	cout<<r<<endl;
	return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘bool check(ll)’:
./Main.cpp:27:17: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   27 |  for (int i=0; i<tt.size(); i++){
      |                ~^~~~~~~~~~
./Main.cpp:32:14: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   32 |    while (top<vc.size() && vc[top].second>=tt[i]){
      |           ~~~^~~~~~~~~~
./Main.cpp:37:14: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   37 |   ll cur=(top==vc.size()?0:vc[top].first);
      |           ~~~^~~~~~~~~~~
./Main.cpp:52:13: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   52 |   while (top<vc.size() && vc[top].second>=tt[i]){
      |          ~~~^~~~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:73:17: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   73 |  for (int i=0; i<tt.size(); i++){
      |                ~^~~~~~~~~~

ジャッジ結果