QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#413127 | #4163. 地精部落 | x-camp | 0 | 3ms | 4260kb | C++17 | 3.3kb | 2024-05-17 07:14:23 | 2024-05-17 07:14:24 |
answer
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <fstream>
#include <cstring>
using namespace std;
#define ar first
#define de second
int N, m1, m2;
#define MX 100005
vector<pair<int,int>> s1, s2;
int parked[MX];
vector<pair<pair<int,int>,pair<int,int>>> t1, t2;
int ans;
int schedule (vector<pair<int,int>> &s, int sz, vector<pair<pair<int,int>,pair<int,int>>> & t) {
if (t.empty()) {
for (int i=0; i<s.size(); i++) {
auto p = s[i];
t.push_back({p,{1,i}});
t.push_back({{p.second,p.first},{2,i}});
}
sort(t.begin(),t.end());
}
vector<int> parkedAir;
vector<bool> in( (int) s.size());
int cur = 0;
int endtime = 0;
int parked = 0;
for (int i=0; i<t.size();i++) {
auto &e = t[i];
if (e.second.first == 1) { // arrival time
if (cur < sz ) {
cur++;
parked++;
parkedAir.push_back(cur);
in[e.second.second] = true; //parked in bridge
}
}
else { // departure time
if (in[e.second.second]) cur --;
}
}
return parked;
}
int res[MX];
void quadSearch(int start, int end) {
if (start ==0)
res[start] = schedule(s1, start, t1) + schedule(s2,N-start , t2);
if (end ==N)
res[end] = schedule(s1, end, t1) + schedule(s2,N-end , t2);
if (end - start <10) {
for (int i = max(0,start - 50); i<=min(N, end+50); i++) {
res[i] = schedule(s1, i, t1) + schedule(s2, N-i, t2);
ans = max(ans, res[i]);
}
} else {
int left = start + (end -start)/4, right = start + (end-start)*3/4;
int mid = (start + end) /2;
int q1 = schedule(s1, left, t1) + schedule(s2,N-left , t2);
int q2 = schedule(s1, mid, t1) + schedule(s2,N-mid , t2);
int q3 = schedule(s1, right, t1) + schedule(s2,N-right , t2);
if (start > q2) {
if (q2 >= q3) quadSearch(start, mid);
else quadSearch(start, right);
}
else if (end > q2) {
if (q2 >= q1) quadSearch(mid, end);
else quadSearch(left, end);
}
else if (q2 > q1 && q2 > q3) quadSearch(left, right);
else if (q1 > q2 && q2 >= q3) quadSearch(start, right);
else if (q3 >= q2 && q2 >=q1) quadSearch(left, end);
else if (res[start] < q1) quadSearch(left, end);
else if (res[end] < q3) quadSearch(start, right);
else {
quadSearch(start,mid);
quadSearch(mid+1, end);
}
}
return;
}
int main() {
cin >> N >> m1 >> m2;
for (int i=0; i<m1; i++) {
int a,b;
cin >> a >> b;
s1.push_back({a,b});
}
for (int i=0; i<m2; i++) {
int a,b;
cin >> a >> b;
s2.push_back({a,b});
}
int best = 0;
/*for (int i=0; i<=N; i++) {
best = max(best, schedule(s1, i,t1) + schedule(s2, N-i,t2));
}*/
quadSearch(0, N);
/*
cout << best << " " << ans << endl;
for (int i=0; i<=N; i++)
cout << res[i] << " ";
cout << endl; */
cout << ans;
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3880kb
input:
9 2811
output:
9
result:
wrong answer 1st lines differ - expected: '1817', found: '9'
Test #2:
score: 0
Wrong Answer
time: 3ms
memory: 3736kb
input:
10 12929
output:
10
result:
wrong answer 1st lines differ - expected: '10539', found: '10'
Test #3:
score: 0
Time Limit Exceeded
input:
17 21929121
output:
result:
Test #4:
score: 0
Wrong Answer
time: 3ms
memory: 4260kb
input:
18 29121
output:
18
result:
wrong answer 1st lines differ - expected: '15047', found: '18'
Test #5:
score: 0
Time Limit Exceeded
input:
200 123849291
output:
result:
Test #6:
score: 0
Time Limit Exceeded
input:
500 182739417
output:
result:
Test #7:
score: 0
Time Limit Exceeded
input:
550 281321834
output:
result:
Test #8:
score: 0
Time Limit Exceeded
input:
2500 18239314
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
4000 129394123
output:
result:
Test #10:
score: 0
Time Limit Exceeded
input:
4200 192340123