QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#403941#8590. Problem Setterstegatxins018 219ms23328kbC++206.4kb2024-05-02 22:26:522024-05-02 22:26:53

Judging History

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

  • [2024-05-02 22:26:53]
  • 评测
  • 测评结果:18
  • 用时:219ms
  • 内存:23328kb
  • [2024-05-02 22:26:52]
  • 提交

answer

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

#ifdef DEBUG
#include "debug.cpp"
#else
#define dbg(...)
#define dbgarr(...)
#endif

using ull = unsigned long long;
using ll = long long;
using vi = vector<int>;
using vll = vector<long long>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vs = vector<string>;
using pii = pair<int, int>;

#define pb push_back
#define ms memset
#define el '\n'
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) ((int)(x).size())

const int INF = 0x3f3f3f3f;
const ll INFL = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#define rep(i, b) for (auto i = 0; i < (b); i++)
#define reps(i, b) for (auto i = 1; i <= (b); i++)
//#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
//#define rreps(i,x) for(int i=((int)(x));i>0;i--)

template<class T> inline void printvec(const vector<T>& v, bool split_line=false, bool ones=false) {
    if(v.empty()){
        cout << "This vector is empty." << el;
        return;
    }
    if(ones){
        for (int i = 1; i <= (int)v.size(); i++) {
            if(v[i]==INF || v[i]==INFL) cout << 'x' << " \n"[split_line || i+1==(int)v.size()];
            else cout << v[i] << " \n"[split_line || i+1==(int)v.size()];
        }
    }else{
        for (int i = 0; i < (int)v.size(); i++) {
            if(v[i]==INF || v[i]==INFL) cout << 'x' << " \n"[split_line || i+1==(int)v.size()];
            else cout << v[i] << " \n"[split_line || i+1==(int)v.size()];
        }
    }
}

const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};
const string stepdir = "URDL";

struct Fast {Fast() {std::cin.tie(0); ios::sync_with_stdio(false);}} fast;
// }}}


struct st_t {
    long long val;
    long long lazy;
    static const long long null_l = 0;

    //initial value, used when er initializing & for returning outside node (but technically it shudnt happen i think)
    st_t(): val(0), lazy(null_l) {}

    //used when initializing given a value
    st_t(long long v): val(v), lazy(null_l) {}

    // used when updating when passing a value v
    st_t(bool lz, long long v): lazy(v) {}

    // push up, used in init, returning update & query
    st_t op(st_t& other) {
        return st_t(max(val,other.val));
    }

    // push up when only one node is in range
    st_t op(bool rhs) {
        return *this;
    }

    // applying lazy, used when reaching the final node in update / when theres lazy in querying
    void lazy_app(int size) {
        if(lazy == null_l)return;
        val = max(val,lazy);
    }

    // used when pushing down lazy to children nodes & combining lazy to target node when updating
    long long lazy_comb(st_t& v) {
        return max(lazy,v.lazy);
    }
};

template <typename num_t> 
struct segtree {
    int n;
    int inline ls(int i){return 2*i+1; }
    int inline rs(int i){return 2*i+2; }
    vector<num_t> tree;

    void init(int s, long long* arr) {
        n = s;
        tree = vector<num_t>(4 * s);
        init(0, 0, n - 1, arr);
    }

    void init(int s) {
        n = s;
        tree = vector<num_t>(4 * s);
    }

    num_t init(int i, int l, int r, long long* arr) {
        if (l == r) return tree[i] = num_t(arr[l]);
        int mid = (l + r) / 2;
        num_t a = init(ls(i), l, mid, arr),
              b = init(rs(i), mid + 1, r, arr);
        return tree[i] = a.op(b);
    }

    void update(int l, int r, long long v) {
        if (l > r) return;
        update(0, 0, n - 1, l, r, num_t(true, v));
    }

    num_t update(int i, int tl, int tr, int ql, int qr, num_t v) {
        eval_lazy(i, tl, tr);
	
        if (tr < ql || qr < tl) return tree[i];
        if (ql <= tl && tr <= qr) {
            tree[i].lazy = tree[i].lazy_comb(v);
            eval_lazy(i, tl, tr);
            return tree[i];
        }

        int mid = (tl + tr) / 2;
        num_t a = update(ls(i), tl, mid, ql, qr, v),
              b = update(rs(i), mid + 1, tr, ql, qr, v);
        return tree[i] = a.op(b);
    }

    num_t query(int l, int r) {
        // if (l > r) return num_t::null_v;
        assert(r >= l);
        return query(0, 0, n-1, l, r);
    }

    num_t query(int i, int tl, int tr, int ql, int qr) {
        eval_lazy(i, tl, tr);

        if (ql <= tl && tr <= qr) return tree[i];

        int mid = (tl + tr) / 2;

        if(mid >= ql && qr >= tl && tr >= ql && qr >= mid+1){
            num_t a = query(ls(i), tl, mid, ql, qr);
            num_t b = query(rs(i), mid + 1, tr, ql, qr);
            return a.op(b);
        }else if(mid >= ql && qr >= tl){
            num_t a = query(ls(i), tl, mid, ql, qr);
            return a.op(false);
        }else if(tr >= ql && qr >= mid+1){
            num_t b = query(rs(i), mid + 1, tr, ql, qr);
            return b.op(true);
        }
        return num_t::null_l; // wont happen kot probably
    }

    void eval_lazy(int i, int l, int r) {
        tree[i].lazy_app(r - l + 1);
        if (l != r) {
            tree[ls(i)].lazy = tree[ls(i)].lazy_comb(tree[i]);
            tree[rs(i)].lazy = tree[rs(i)].lazy_comb(tree[i]);
        }
        tree[i].lazy = num_t::null_l;

    }
};


const int mxN = 200001;
segtree<st_t> st;

int n,m;
int main() {
    cin >> n >> m;
    vector<ll> mq(n),sat(n),q(m),d(m);
    for(int i=0; i<n; i++){
        cin >> mq[i] >> sat[i];
    }
    vector<ll> tmp(mq);
    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    st.init(n);
    for(int i = 0; i < n; i++){
        mq[i] = lower_bound(tmp.begin(), tmp.end(), mq[i]) - tmp.begin();
        st.update(mq[i],mq[i],sat[i]);
    }
    dbg(st.query(0,n).val);

    ll ans = 0;
    for(int i = 0; i < m; i++){
        cin >> q[i] >> d[i];
        q[i] = upper_bound(tmp.begin(), tmp.end(), q[i]) - tmp.begin() - 1;
        // if(q[i]<0)q[i] = 0;
        ans += max(0LL,st.query(0,q[i]).val - d[i]);
        dbg(ans,d[i]);
    }
    cout << ans << el;


}

/*
 *
 sort all problem by its quality
 for each problem
 look for the largest satisfication among all contest who overcome min


 
 */

詳細信息

Subtask #1:

score: 18
Accepted

Test #1:

score: 18
Accepted
time: 1ms
memory: 3604kb

input:

1000 1
570339 324084
75781 292531
427864 843267
928484 613828
883296 385343
733451 782070
756314 89477
786410 133722
455015 841750
146307 536680
992681 107898
657731 633895
764691 258779
142935 640379
445046 717170
227758 578083
526095 660806
859673 757597
898726 4088
719881 887973
850810 674331
752...

output:

575102

result:

ok single line: '575102'

Test #2:

score: 18
Accepted
time: 1ms
memory: 3620kb

input:

1000 1
93555 337906
136252 661901
127242 762569
370437 288257
767189 41343
788899 716075
654667 69573
991915 927883
7763 509983
986424 963695
362599 476740
955459 125250
620759 316409
611815 579388
450941 792473
270525 969538
184881 646954
624056 237034
592281 938786
454775 905658
805770 146630
6691...

output:

266314

result:

ok single line: '266314'

Test #3:

score: 18
Accepted
time: 1ms
memory: 3624kb

input:

1000 1
372915 410729
261932 931394
243312 331965
724590 783322
487345 73014
917626 421202
52572 541824
13651 326164
162767 857461
39807 712157
363164 412246
748463 240053
627875 449914
356280 426806
472871 238292
317364 708065
530316 302867
985730 776991
389066 595962
383264 231238
755140 612569
900...

output:

18699

result:

ok single line: '18699'

Test #4:

score: 18
Accepted
time: 1ms
memory: 3644kb

input:

1000 1
973869 701086
558011 774964
697322 753066
791372 665308
8732 871957
842731 544161
846847 511267
48968 129792
601946 266150
80870 311886
436651 574009
696653 679800
550300 95648
733297 433189
20014 746152
691080 377304
797922 412118
753742 696618
374002 692110
676184 965244
896440 485847
25751...

output:

225812

result:

ok single line: '225812'

Test #5:

score: 18
Accepted
time: 1ms
memory: 3628kb

input:

1000 1
446735 220359
691517 839587
111030 978505
365818 886684
984994 25626
759094 161155
535967 370952
202441 528116
458607 347342
321712 893280
511738 62329
945252 466145
434938 569254
923698 152927
434132 616641
158841 717741
35249 127470
952799 690934
451125 357306
320955 931834
709677 396258
42...

output:

907138

result:

ok single line: '907138'

Test #6:

score: 18
Accepted
time: 0ms
memory: 3624kb

input:

1000 1
601061 798635
853232 805018
903746 742357
851779 891012
871518 591965
787106 438276
800008 833789
97461 455880
918209 71464
738824 721438
142105 117316
651442 950621
469940 155734
390371 819443
864285 858331
667676 294253
995541 511904
673777 634772
669846 669616
85323 280317
517325 300991
79...

output:

759810

result:

ok single line: '759810'

Test #7:

score: 18
Accepted
time: 1ms
memory: 3580kb

input:

1000 1
475214 435913
79469 670572
187835 156303
287622 752976
668304 570286
851398 338524
637600 938147
883397 950768
17064 623512
444573 908727
365435 776654
889223 984546
804670 743408
169630 395052
347470 433540
105900 181524
678796 566786
953677 639129
29480 630407
43286 936697
320068 162363
552...

output:

719341

result:

ok single line: '719341'

Test #8:

score: 18
Accepted
time: 1ms
memory: 3864kb

input:

1000 1
934730 460637
249010 431133
278189 613881
957564 521984
736935 332621
703360 564511
118172 714420
947838 878574
178322 44348
11458 606815
34008 385140
13323 140563
679510 670674
82238 970202
244493 99898
960974 433944
531664 48342
586720 74325
527854 988420
560251 926189
992269 510883
858041 ...

output:

462952

result:

ok single line: '462952'

Test #9:

score: 18
Accepted
time: 1ms
memory: 3656kb

input:

1000 1
38704 346504
483075 126353
822919 268051
576702 147796
753513 132648
592287 492765
172980 356260
865509 450281
978835 204094
829982 450140
332545 150541
744383 403569
705398 73425
307433 347343
119867 23193
820121 126158
69812 51140
704003 291934
167826 477177
271495 349467
658879 329028
5147...

output:

0

result:

ok single line: '0'

Test #10:

score: 18
Accepted
time: 1ms
memory: 3584kb

input:

1000 1
885301 271328
384259 13091
411940 185829
915824 306781
143642 88748
85829 245942
919389 73320
501732 402705
35599 44992
771955 383893
47482 449389
803506 311468
855254 280722
158647 224849
896120 201358
987243 268364
657053 147875
855508 280614
718336 89658
123939 2017
218272 414547
715521 20...

output:

0

result:

ok single line: '0'

Test #11:

score: 18
Accepted
time: 0ms
memory: 3556kb

input:

5 1
3 4
1 2
5 6
2 8
4 0
3 6

output:

2

result:

ok single line: '2'

Subtask #2:

score: 0
Runtime Error

Dependency #1:

100%
Accepted

Test #12:

score: 0
Runtime Error

input:

1000 1000
389868 910117
138872 863197
945257 314232
767951 66789
16890 292700
183331 674706
406355 902607
544759 783299
202033 367674
144750 418158
965750 393368
848676 358716
67427 711157
128330 967985
223199 421907
386765 736937
238840 373101
229494 95780
28597 7848
65650 153531
388679 260846
3364...

output:


result:


Subtask #3:

score: 0
Runtime Error

Test #24:

score: 26
Accepted
time: 219ms
memory: 23328kb

input:

200000 200000
443848 257048
353855 430518
112240 460358
489050 850745
18217 643349
796031 335731
553602 81823
556808 39341
963397 797473
713023 273372
888193 500234
801660 980841
416233 163140
649254 659678
434013 461662
805451 259446
107168 839690
438518 100393
584335 435627
735040 11809
906814 672...

output:

199985649927

result:

ok single line: '199985649927'

Test #25:

score: 0
Runtime Error

input:

200000 200000
333130 577648
41080 822997
187466 358241
16874 51949
553684 775680
888225 58652
283594 632965
971667 522676
73986 76332
905359 631172
633389 994061
934283 902840
110896 341628
432967 332824
239445 649641
689728 484799
124192 63092
153968 530823
906578 363019
287528 659642
141227 738119...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%