QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#71417#5258. MortgageSorting#WA 10ms22596kbC++2.2kb2023-01-09 23:39:502023-01-09 23:39:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-09 23:39:52]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:22596kb
  • [2023-01-09 23:39:50]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef __int128 ll;
const ll MX = 1e18;
const int N = 2e5 + 3;

int n, m, a[N];
ll p[N];

ll area2(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3){
	return x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2;
}

ll area2(pair<ll, ll> p1, pair<ll, ll> p2, pair<ll, ll> p3){
	return area2(p1.first, p1.second, p2.first, p2.second, p3.first, p3.second);
}

struct ConvexHull{
	vector<pair<ll, ll>> v;
	ConvexHull(){}
	ConvexHull(const vector<pair<ll, ll>> v2){
		for(int i = 0; i < v2.size(); ++i){
			while(v.size() >= 2 && area2(v[v.size() - 2], v[v.size() - 1], v2[i]) <= 0){
				v.pop_back();
			}
			v.push_back(v2[i]);
		}
	}
	ll queryPoint(ll x, ll y, pair<ll, ll> p){
		x = p.first - x;
		y = p.second - y;
		if(y < 0)
			return -1;
		return y / x;
	}
	ll query(ll x, ll y){
		if(v.empty()) return MX;
		int l = 0, r = (int)v.size() - 1;
		while((r - l) > 2){
			int mid1 = (2 * l + r) / 3;
			int mid2 = (l + 2 * r) / 3;
			if(queryPoint(x, y, v[mid1]) <= queryPoint(x, y, v[mid2]))
				r = mid2;
			else
				l = mid1;
		}
		ll res = MX;
		for(int i = l; i <= r; ++i)
			res = min(res, queryPoint(x, y, v[i]));
		return res;
	}
};

struct SegmentTree{
	ConvexHull ch[4 * N];

	void init(int i = 0, int l = 1, int r = n){
		vector<pair<ll, ll>> v(r - l + 1);
		for(int j = l; j <= r; ++j)
			v[j - l] = pair<ll, ll>{j, p[j]};
		ch[i] = ConvexHull(v);

		if(l == r) return;
		int mid = (l + r) >> 1;
		init(2 * i + 1, l, mid);
		init(2 * i + 2, mid + 1, r);
	}

	ll query(int sl, int sr, ll x, ll y, int i = 0, int l = 1, int r = n){
		if(sr < l || r < sl) return MX;
		if(sl <= l && r <= sr) return ch[i].query(x, y);
		int mid = (l + r) >> 1;
		return min(query(sl, sr, x, y, 2 * i + 1, l, mid), query(sl, sr, x, y, 2 * i + 2, mid + 1, r));
	}
} st;

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

	cin >> n >> m;
	for(int i = 1; i <= n; ++i)
		cin >> a[i];
	for(int i = 1; i <= n; ++i)
		p[i] = a[i] + p[i - 1]; 

	st.init();

	for(int i = 1; i <= m; ++i){
		int s, k;
		cin >> s >> k;

		int l = s, r = s + k - 1;
		ll t = st.query(l, r, l - 1, p[l - 1]);
		int ans = (int)t;
		if(ans == -1)
			cout << "stay with parents\n"; 
		else
			cout << ans << "\n";
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 10ms
memory: 22412kb

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:

ok 10 lines

Test #2:

score: -100
Wrong Answer
time: 4ms
memory: 22596kb

input:

1000 1000
196 207 195 207 200 203 202 204 205 191 190 188 203 198 201 188 203 198 196 196 200 195 200 206 193 198 186 196 200 185 202 195 203 199 185 199 202 191 184 194 195 194 193 195 184 197 189 193 186 187 193 193 196 186 195 193 186 192 188 188 187 197 179 188 195 196 197 186 194 183 189 185 19...

output:

158
16
110
64
160
118
169
63
172
128
93
82
118
119
86
32
174
145
139
84
149
120
133
155
108
110
65
178
90
99
118
91
133
85
151
76
130
50
91
99
96
78
110
87
119
141
68
81
172
82
112
139
136
81
79
16
51
31
104
116
108
38
75
176
156
55
165
112
146
74
68
172
112
157
94
177
111
166
110
112
98
155
109
155...

result:

wrong answer 41st lines differ - expected: '95', found: '96'