QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#413127#4163. 地精部落x-camp0 3ms4260kbC++173.3kb2024-05-17 07:14:232024-05-17 07:14:24

Judging History

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

  • [2024-05-17 07:14:24]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:4260kb
  • [2024-05-17 07:14:23]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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

output:


result: