QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134682#2442. Welcome Partyckiseki#WA 865ms23776kbC++142.1kb2023-08-04 14:56:382023-08-04 14:56:41

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-04 14:56:41]
  • 评测
  • 测评结果:WA
  • 用时:865ms
  • 内存:23776kb
  • [2023-08-04 14:56:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; L++)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else 
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        multiset<int64_t> aval, must;
        map<int64_t, vector<int64_t>> a;
        for (int i = 0; i < n; ++i) {
            int64_t x, y;
            cin >> x >> y;
            a[x].push_back(y);
            aval.insert(y);
        }
        int64_t ans = numeric_limits<int64_t>::max();
        for (auto it = a.rbegin(); it != a.rend(); ++it) {
            multiset<int64_t> cur;
            int64_t x = it->first;
            for (auto y : it->second)
                cur.insert(y);

            auto upd = [x, &ans](const multiset<int64_t> &s) {
                auto it = s.lower_bound(x);
                if (it != s.end()) {
                    ans = min(ans, *it - x);
                }
                if (it != s.begin()) {
                    ans = min(ans, x - *prev(it));
                }
            };
            
            for (auto y : it->second) {
                cur.erase(cur.find(y));
                if (not must.empty() and *must.rbegin() >= x) {
                    ans = min(ans, *must.rbegin() - x);
                } else {
                    upd(must);
                    upd(cur);
                    upd(aval);
                }
                cur.insert(y);
            }

            for (auto y : cur)
                must.insert(y);
        }
        cout << ans << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 865ms
memory: 23776kb

input:

66
5
27 46
89 13
55 8
71 86
22 35
3
3 5
4 7
6 2
2
0 1000000000
1000000000 0
2
1000000000 0
0 1000000000
2
1000000000 0
1000000000 0
2
0 1000000000
0 1000000000
2
1000000000 1000000000
0 0
2
0 0
0 0
2
1000000000 1000000000
1000000000 1000000000
3
90 30
90 50
90 85
3
0 0
0 2
0 5
3
20 30
20 50
20 70
3
...

output:

3
1
0
0
1000000000
1000000000
0
0
0
5
0
10
5
10
3
0
10
5
0
5
0
10
5
10
3
0
10
5
0
146595730144168239
10974087366700578
21076180420813408
183538167814754058
46751451188711820
62041883297011888
23639646046527434
40476687889457528
189833376395849599
139940820548070767
21494649603533736
1002005362856886...

result:

wrong answer 7th lines differ - expected: '1000000000', found: '0'