ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#205099 | #3646. 调分 | nullptr_qwq | 100 | 2374ms | 30952kb | C++11 | 2.0kb | 2024-06-23 11:01:51 | 2024-06-23 13:04:03 |
answer
// 私は猫です
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define dF(i,a,b) for(int i=(a);i>=(b);i--)
#define wh(lzm) while(lzm--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
using namespace std;
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
inline void chkmax(int &x,int y){ x=max(x,y); }
inline void chkmin(int &x,int y){ x=min(x,y); }
const int mod=998244353,maxn=500005;
int qx[maxn],qy[maxn],a[maxn],li[maxn],ri[maxn],n,m,lim[maxn],ins[maxn];
vector<int>vec[maxn];
void solve(){
n=read(),m=read();
F(i,1,n) a[i]=read(),li[i]=read(),ri[i]=read()+1;
F(i,1,m) qx[i]=read(),qy[i]=read();
set<int>s;
map<int,int>mp;
s.insert(1),s.insert(inf+5);
F(i,1,m) s.insert(qx[i]);
int cnt=0;
for(auto it=s.begin();it!=s.end();++it) mp[*it]=++cnt;
F(i,1,n) {
auto it=s.upper_bound(li[i]);
if(it!=s.begin()) li[i]=mp[*prev(it)];
else li[i]=1;
}
F(i,1,n) {
auto it=s.upper_bound(ri[i]);
ri[i]=mp[*prev(it)];
}
F(i,1,cnt) lim[i]=inf;
F(i,1,m) chkmin(lim[mp[qx[i]]],qy[i]);
F(i,2,m) chkmin(lim[i],lim[i-1]);
F(i,1,n) vec[ri[i]].push_back(li[i]);
int ans=0,num=0;
multiset<int>st;
dF(i,cnt,1){
for(int j:vec[i]) st.insert(j),++ans;
if(i==1)break;
while(num+(int)st.size()>lim[i]){
auto it=st.begin();
ins[*it]++,st.erase(it),--ans;
}
num+=ins[i];
if(num+(int)st.size()>lim[i]) {
int t=lim[i]-st.size();
ans-=num-t,num=t;
}
}
printf("%d",ans);
}
signed main(){
int sjy=1;
cmh(sjy) solve();
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 3ms
memory: 12948kb
input:
15 20 845403345 390609697 980384063 186743724 104990508 963496192 263966340 55953443 787815158 16843...
output:
11
result:
ok single line: '11'
Test #2:
score: 5
Accepted
time: 0ms
memory: 12948kb
input:
15 20 710914207 97234432 738264088 42243279 26728414 621680880 162908406 61586483 185903807 39356031...
output:
8
result:
ok single line: '8'
Test #3:
score: 5
Accepted
time: 3ms
memory: 12948kb
input:
15 20 700412807 672433278 902231896 862757701 298427492 916841742 374302689 72499348 943626637 99857...
output:
11
result:
ok single line: '11'
Test #4:
score: 5
Accepted
time: 0ms
memory: 12952kb
input:
15 20 293265775 187997853 409823298 5464414 1343941 440699330 960988144 265922201 963233253 94420468...
output:
8
result:
ok single line: '8'
Test #5:
score: 5
Accepted
time: 0ms
memory: 12952kb
input:
15 20 461991159 231524604 559439691 5940502 5556321 345367655 903635605 249803497 922750941 22099036...
output:
13
result:
ok single line: '13'
Test #6:
score: 5
Accepted
time: 5ms
memory: 12964kb
input:
200 20 526801273 451267596 669703900 117452796 52230219 581138048 986865963 924965003 996753167 3894...
output:
180
result:
ok single line: '180'
Test #7:
score: 5
Accepted
time: 6ms
memory: 12968kb
input:
200 20 697923362 12116150 916555730 164808860 137308876 177851204 848793719 656245263 936591222 2852...
output:
180
result:
ok single line: '180'
Test #8:
score: 5
Accepted
time: 0ms
memory: 12960kb
input:
200 20 161787269 2568546 247988992 585198193 135846344 900057943 616735835 226367000 704675057 61717...
output:
171
result:
ok single line: '171'
Test #9:
score: 5
Accepted
time: 6ms
memory: 12984kb
input:
200 200 657239333 380683702 843825391 528714786 13173880 984499662 475669898 456612694 833254921 494...
output:
140
result:
ok single line: '140'
Test #10:
score: 5
Accepted
time: 11ms
memory: 12976kb
input:
200 200 909293380 560881903 968880531 971017373 170045342 974022370 65272918 29942253 432191198 6343...
output:
119
result:
ok single line: '119'
Test #11:
score: 5
Accepted
time: 0ms
memory: 12980kb
input:
200 200 939041723 556876806 957997424 697350341 455737278 746435146 445674199 362307255 658553145 14...
output:
174
result:
ok single line: '174'
Test #12:
score: 5
Accepted
time: 6ms
memory: 12980kb
input:
200 200 797241149 541897259 988623827 286876319 100634468 629979548 706691378 249253522 768355649 53...
output:
158
result:
ok single line: '158'
Test #13:
score: 5
Accepted
time: 194ms
memory: 28356kb
input:
100000 100000 113998910 1 427605660 605845930 1 705422321 151459006 1 883297089 387565910 1 76233795...
output:
80577
result:
ok single line: '80577'
Test #14:
score: 5
Accepted
time: 215ms
memory: 30028kb
input:
100000 100000 254892569 1 447083628 483853444 1 731264529 334949412 1 349769789 990131147 1 99641344...
output:
91658
result:
ok single line: '91658'
Test #15:
score: 5
Accepted
time: 329ms
memory: 30860kb
input:
100000 100000 681865203 340942769 927067423 862581764 707438427 956358388 116698514 8707590 75316147...
output:
91886
result:
ok single line: '91886'
Test #16:
score: 5
Accepted
time: 283ms
memory: 29204kb
input:
100000 100000 261331494 48983905 881868750 781830534 695641946 888787608 53260475 3830725 603231233 ...
output:
61713
result:
ok single line: '61713'
Test #17:
score: 5
Accepted
time: 305ms
memory: 30600kb
input:
100000 100000 293506655 235651927 491497166 438822357 265156420 853923925 751934202 175188320 797954...
output:
87719
result:
ok single line: '87719'
Test #18:
score: 5
Accepted
time: 309ms
memory: 30188kb
input:
100000 100000 842554959 79038413 923174446 409500140 348943344 708184830 167573117 117904906 7803893...
output:
80630
result:
ok single line: '80630'
Test #19:
score: 5
Accepted
time: 292ms
memory: 30904kb
input:
100000 100000 228364413 22596352 445742699 624348298 29932170 795936020 608997744 551190379 83387823...
output:
92773
result:
ok single line: '92773'
Test #20:
score: 5
Accepted
time: 407ms
memory: 30952kb
input:
100000 100000 482819933 162045322 954408191 299330487 19663334 576950439 84528908 37965318 245372349...
output:
93410
result:
ok single line: '93410'
Extra Test:
score: 0
Extra Test Passed