QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#618664#2774. SceneryCharizard2021WA 0ms3828kbC++142.3kb2024-10-07 02:44:452024-10-07 02:44:45

Judging History

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

  • [2024-10-07 02:44:45]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3828kb
  • [2024-10-07 02:44:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, t;
    cin >> n >> t;
    vector<pair<int, int> > v(n);
    vector<int> x;
    for(int i = 0; i < n; i++){
        cin >> v[i].first >> v[i].second;
        x.push_back(v[i].first);
        x.push_back(v[i].second);
    }
    sort(x.begin(), x.end());
    int idx = unique(x.begin(), x.end()) - x.begin();
    vector<int> v2[idx];
    for(int i = 0; i < n; i++){
        v[i].first = lower_bound(x.begin(), x.begin() + idx, v[i].first) - x.begin() + 1;
        v[i].second = lower_bound(x.begin(), x.begin() + idx, v[i].second) - x.begin() + 1;
        v2[v[i].first].push_back(v[i].second);
    }
    vector<int> counter(idx, 0);
    vector<int> val1(idx);
    for(int j = 0; j < idx; j++){
        val1[j] = x[j];
    }
    vector<int> positions(idx, idx);
    vector<int> things(idx, 1e9);
    vector<int> cur(idx);
    bool works = true;
    for(int i = idx - 1; i >= 0; i--){
        if(!v2[i].empty()){
            for(int j = 0; j < idx; j++){
                cur[j] = things[j];
            }
            for(int j : v2[i]){
                for(int k = j; k < idx; k++){
                    counter[k]++;
                }
            }
            for(int j = idx - 1; j >= i; j--){
                for(int a = 0; a < counter[j]; a++){
                    val1[j] -= t;
                    while(positions[j] && val1[j] < x[positions[j]]){
                        if(val1[j] < x[i]){
                            works = false;
                            break;
                        }
                        val1[j] = min(val1[j], cur[positions[j]]);
                        positions[j]--;
                    }
                    if(!works){
                        break;
                    }
                    if(val1[j] < x[i]){
                        works = false;
                        break;
                    }
                    things[i] = min(things[i], val1[j] - t);
                }
                if(!works){
                    break;
                }
                counter[j] = 0;
            }
            if(!works){
                break;
            }
        }
        if(!works){
            break;
        }
    }
    if(works){
        cout << "yes\n";
    }
    else{
        cout << "no\n";
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3528kb

input:

2 10
0 15
5 20

output:

yes

result:

ok single line: 'yes'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

2 10
1 15
0 20

output:

no

result:

ok single line: 'no'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

2 10
5 30
10 20

output:

yes

result:

ok single line: 'yes'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3828kb

input:

11 6
0 74
2 60
4 34
10 36
21 46
26 40
28 38
30 48
50 68
52 68
54 62

output:

no

result:

wrong answer 1st lines differ - expected: 'yes', found: 'no'