QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#639811#1751. Automatic Accountantoxford01#WA 67ms12104kbC++202.7kb2024-10-13 22:53:062024-10-13 22:53:07

Judging History

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

  • [2024-10-13 22:53:07]
  • 评测
  • 测评结果:WA
  • 用时:67ms
  • 内存:12104kb
  • [2024-10-13 22:53:06]
  • 提交

answer

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

#define rep(i, a, b) for (auto i = a; i < (b); ++i)
#define repr(i, a, b) for (auto i = (a) - 1; i >= (b); --i)
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;

template<class T>
inline bool cmax(T &a, const T& b) {
    return a < b ? a = b, 1 : 0;
}

template<class T>
inline bool cmin(T &a, const T &b) {
    return b < a ? a = b, 1 : 0;
}

const int inf = 0x3f3f3f3f;
const ll linf = 1e18;
const double dinf = numeric_limits<double>::infinity();

struct SegmentTree {
    typedef int T;
    static constexpr T unit = INT_MIN;
    T f(T a, T b) { return max(a, b); }
    vector<T> s; int n;
    SegmentTree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
    void update(int pos, T val) {
        for (s[pos += n] = val; pos /= 2; )
            s[pos] = f(s[pos*2], s[pos*2+1]);
    }
    T get(int b, int e) {
        T ra = unit, rb = unit;
        for (b += n, e+= n; b < e; b /= 2, e/= 2) {
            if (b%2) ra = f(ra, s[b++]);
            if (e%2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};

/*struct SegmentTree {
    vi t;
    int n;

    SegmentTree(int n) {
        t = vi(4*n, INT_MIN);
    }

    void update(int v, int tl, int tr, int pos, int x) {
        if ()
    }

    int get(int v, int tl, int tr, int l, int r) {

    }
};*/

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int s;
    cin >> s;
    vpii ab(s);
    map<int, vpii> a;
    for (int i = 0; i< s; i++) {
        cin >> ab[i].first >> ab[i].second;
        a[ab[i].second].pb({ab[i].first, i});
    }
    int c;
    cin >> c;
    vpii coins(c);
    for (int i = 0; i< c; i++) {
        cin >> coins[i].second >> coins[i].first; // Its swapped Importnant
    }

    sort(all(coins));

    SegmentTree tree(s); // MAx tree
    int res = 0;
    int prev = 0;
    for (int i = 0; i < c; i++) {
        for (int j = prev; j <= coins[i].first; j++) {
            for (auto x : a[j]) {
                tree.update(x.second, x.first);
            }
        }
        prev = coins[i].first+1;

        int lo = 0, hi = s-1, ans = s-1, mid;
        while (lo <= hi) {
            mid = (lo+hi)/2;

            bool check = tree.get(0, mid+1) >= coins[i].second;
            if (check) {
                ans = mid;
                hi = mid - 1;
            } else
                lo = mid + 1;
        }
        
        res += ans+1;
    }

    cout << res << endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3784kb

input:

1000
536 243
561 59
685 484
59 909
90 456
205 685
313 978
614 29
484 610
394 893
998 877
731 595
266 588
153 356
169 602
604 324
971 194
965 378
737 456
910 649
226 559
472 713
24 884
467 110
199 915
129 792
103 775
266 740
499 689
605 322
778 534
320 458
607 625
351 896
543 924
658 412
393 642
89 5...

output:

34010

result:

ok single line: '34010'

Test #2:

score: 0
Accepted
time: 19ms
memory: 4888kb

input:

50000
425 40
487 864
387 101
298 69
613 779
697 748
259 619
490 799
544 967
559 280
968 243
408 210
963 195
764 720
621 469
362 572
253 653
547 326
832 233
600 111
284 287
135 925
398 919
730 156
620 327
156 887
390 406
488 267
159 126
788 476
886 896
344 386
324 30
76 207
674 505
248 924
324 995
17...

output:

2225901

result:

ok single line: '2225901'

Test #3:

score: -100
Wrong Answer
time: 67ms
memory: 12104kb

input:

100000
344 70883
664 5149
547 56373
734 77762
942 85742
576 16116
697 36821
483 86461
842 33224
171 80225
261 66481
150 98557
96 74605
871 7563
688 62312
276 14306
327 28166
879 41516
342 91811
795 47532
21 54376
557 34066
609 42833
385 58831
166 76728
775 62803
431 97310
181 87000
335 34912
999 841...

output:

657493213

result:

wrong answer 1st lines differ - expected: '4952460509', found: '657493213'