QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#403940 | #8590. Problem Setter | stegatxins0 | 18 | 203ms | 23300kb | C++20 | 6.4kb | 2024-05-02 22:25:27 | 2024-05-02 22:25:28 |
Judging History
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);
int 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
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 18
Accepted
Test #1:
score: 18
Accepted
time: 1ms
memory: 3884kb
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: 0
Accepted
time: 1ms
memory: 3708kb
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: 0
Accepted
time: 1ms
memory: 3912kb
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: 0
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: 0
Accepted
time: 1ms
memory: 3936kb
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: 0
Accepted
time: 1ms
memory: 3844kb
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: 0
Accepted
time: 1ms
memory: 3924kb
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: 0
Accepted
time: 1ms
memory: 3584kb
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: 0
Accepted
time: 1ms
memory: 3692kb
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: 0
Accepted
time: 0ms
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: 0
Accepted
time: 0ms
memory: 3544kb
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
Wrong Answer
Test #24:
score: 0
Wrong Answer
time: 203ms
memory: 23300kb
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:
-1877812985
result:
wrong answer 1st lines differ - expected: '199985649927', found: '-1877812985'
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%