QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#327945#5258. MortgageTerdyWA 6ms22896kbC++141.9kb2024-02-15 15:40:572024-02-15 15:40:57

Judging History

你现在查看的是最新测评结果

  • [2024-02-15 15:40:57]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:22896kb
  • [2024-02-15 15:40:57]
  • 提交

answer

# include <bits/stdc++.h>

using namespace std;

# define int long long

# define PII pair< int , int >
# define MP make_pair
# define fi first
# define se second

const int N = 2e5 + 5;
int n , m , a[N];

vector< PII > operator + (vector< PII > a , vector< PII > b)
{
	vector< PII > c = a;
	for(auto t : b)
	{
		int siz = c.size();
		while(siz >= 2 && 1ll * (t.se - c[siz - 1].se) * (t.fi - c[siz - 2].fi) < 1ll * (t.se - c[siz - 2].se) * (t.fi - c[siz - 1].fi)) c.pop_back() , siz--;
		c.push_back(t);
	}
	return c;
}

struct Seg
{
	vector< PII > vec[N<<2];
# define lc x << 1
# define rc x << 1 | 1
# define mid (l + r >> 1)
	void PushUp(int x) {vec[x] = vec[lc] + vec[rc];}
	void Build(int x , int l , int r)
	{
		if(l == r) return vec[x].emplace_back(l , a[l]) , void();
		Build(lc , l , mid) , Build(rc , mid + 1 , r);
		PushUp(x);
	}
	vector< PII > Query(int x , int l , int r , int L , int R)
	{
		if(L <= l && r <= R) return vec[x];
		if(mid < L) return Query(rc , mid + 1 , r , L , R);
		if(mid >= R) return Query(lc , l , mid , L , R);
		return Query(lc , l , mid , L , R) + Query(rc , mid + 1 , r , L , R);
	}
} tr;

signed main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i] , a[i] += a[i - 1];
	tr.Build(1 , 1 , n);
	for(int i = 1; i <= m; i++)
	{
		int s , t , l , r , ans;
		cin >> s >> t , t = s + t - 1;
		vector< PII > vec = tr.Query(1 , 1 , n , s , t);
		// for(auto t : vec) cout << t.fi << ' ' << t.se << endl;
		l = 0 , r = vec.size() - 1;
		if(vec.size() == 1) cout << '*';
		while(l <= r)
		{
			if(mid == 0) {ans = 0 , l = 1; continue ;}
			if(1ll * (vec[mid].se - a[s - 1]) * (vec[mid - 1].fi - s + 1) <= 1ll * (vec[mid - 1].se - a[s - 1]) * (vec[mid].fi - s + 1)) ans = mid , l = mid + 1;
			else r = mid - 1;
		}
		ans = (vec[ans].se - a[s - 1]) / (vec[ans].fi - s + 1);
		if(ans < 0) cout << "stay with parents\n";
		else cout << ans << '\n';
	}
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 22896kb

input:

10 10
21 18 19 18 16 15 13 13 13 10
10 1
6 4
7 3
2 2
6 5
2 6
3 2
4 1
1 5
6 3

output:

*10
13
13
18
12
16
18
*18
18
13

result:

wrong answer 1st lines differ - expected: '10', found: '*10'