QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412950 | #8672. 排队 | g1ove | 0 | 363ms | 71304kb | C++14 | 1.9kb | 2024-05-16 22:06:25 | 2024-05-16 22:06:26 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
const int inf=1e9+5;
int n,m;
int l[N],r[N];
int stk[N],top;
struct segtree{
int tr[N*4],lz[N*4],p[N*4];
void Pushup(int x)
{
if(tr[x*2]<=0) tr[x]=tr[x*2],p[x]=p[x*2];
else tr[x]=tr[x*2+1],p[x]=p[x*2+1];
}
void Pushdown(int x)
{
if(!lz[x]) return;
tr[x*2]+=lz[x];
tr[x*2+1]+=lz[x];
lz[x*2]+=lz[x];
lz[x*2+1]+=lz[x];
lz[x]=0;
}
void modify(int l,int r,int L,int R,int x,int v)
{
if(l>R||r<L) return;
if(l>=L&&r<=R)
{
tr[x]+=v;
lz[x]+=v;
if(l==r) p[x]=l;
return;
}
int mid=(l+r)/2;
Pushdown(x);
modify(l,mid,L,R,x*2,v);
modify(mid+1,r,L,R,x*2+1,v);
Pushup(x);
}
int query(int l,int r,int p,int x)
{
if(l==r) return tr[x];
int mid=(l+r)/2;
Pushdown(x);
if(p<=mid) return query(l,mid,p,x*2);
else return query(mid+1,r,p,x*2+1);
}
}tr1,tr2,tr3;
int ans[N];
struct node{
int p,id;
};
vector<node> E[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&l[i],&r[i]),
tr1.modify(1,n,i,i,1,inf),
tr2.modify(1,n,i,i,1,inf);
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
E[l].push_back((node){r,i});
}
for(int i=n;i>=1;i--)
{
tr1.modify(1,n,i,i,1,l[i]-inf);
tr2.modify(1,n,i,i,1,r[i]+1-inf);
while(1)
{
int l1=tr1.p[1],l2=tr2.p[1];
if(tr1.tr[1]>0&&tr2.tr[1]>0) break;
if(tr1.tr[1]>0) l1=inf;
if(tr2.tr[1]>0) l2=inf;
if(l1<l2)
{
tr1.modify(1,n,l1,l1,1,inf);
tr1.modify(1,n,l1+1,n,1,-1);
tr2.modify(1,n,l1+1,n,1,-1);
tr3.modify(1,n,l1,n,1,1);
}
else
{
tr2.modify(1,n,l2,l2,1,inf);
tr1.modify(1,n,l2+1,n,1,1);
tr2.modify(1,n,l2+1,n,1,1);
tr3.modify(1,n,l2,n,1,-1);
}
}
for(auto u:E[i]) ans[u.id]=tr3.query(1,n,u.p,1);
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 3ms
memory: 44196kb
input:
3 3 0 0 1 2 0 2 1 1 1 3 2 3
output:
1 3 1
result:
ok 3 number(s): "1 3 1"
Test #2:
score: -10
Wrong Answer
time: 8ms
memory: 45296kb
input:
5000 5000 5 10 3 9 3 8 2 7 2 5 3 6 1 5 0 2 7 8 2 10 0 3 3 6 4 6 1 6 4 8 7 8 2 7 3 4 4 9 7 8 2 9 2 5 3 6 0 5 6 7 1 2 2 4 2 10 1 5 7 9 6 9 2 3 9 10 5 5 2 9 3 3 2 7 2 4 0 6 0 3 1 7 7 7 4 8 2 9 4 8 0 10 1 8 1 1 2 7 5 9 1 7 1 7 1 4 2 4 1 4 2 9 1 7 4 7 3 8 1 3 4 6 1 5 1 6 0 0 3 9 4 7 2 8 1 8 1 2 7 8 2 7 2...
output:
316 109 875 260 52 825 1362 1219 193 65 204 161 1507 165 505 374 756 854 1051 660 480 58 682 920 140 497 21 21 680 1275 1310 244 628 229 401 870 15 366 1116 392 53 1005 337 781 973 24 999 340 558 459 301 237 458 375 338 902 460 106 725 339 894 1031 411 418 699 1153 677 754 905 613 46 732 565 722 726...
result:
wrong answer 1st numbers differ - expected: '11', found: '316'
Subtask #2:
score: 0
Wrong Answer
Test #12:
score: 0
Wrong Answer
time: 238ms
memory: 65500kb
input:
200000 200000 3 6 3 3 6 10 1 7 2 7 6 9 4 6 3 4 0 8 0 6 3 5 3 4 1 8 7 8 4 5 0 3 1 5 2 9 1 2 1 2 3 4 5 7 6 10 3 9 4 7 1 6 2 6 1 7 2 5 1 7 6 8 1 1 0 7 7 8 0 9 1 7 3 8 3 7 1 2 4 8 5 6 0 6 5 6 2 7 2 6 0 6 0 6 1 7 2 5 0 3 0 3 7 10 3 8 0 2 3 4 3 7 4 9 0 6 4 7 2 6 8 10 2 10 4 10 3 3 2 6 4 5 3 9 1 8 1 2 2 9 ...
output:
47280 56522 45423 9639 12949 1423 51335 31714 52156 25463 64894 33224 4934 50146 65911 54609 6068 29679 24017 15224 3369 13400 15278 43780 1717 2778 35607 33387 22383 21666 23362 33345 46769 34391 14125 56772 55523 28810 64343 37752 40033 25497 25993 47075 647 29761 65142 48211 12855 12276 18188 331...
result:
wrong answer 1st numbers differ - expected: '11', found: '47280'
Subtask #3:
score: 0
Wrong Answer
Test #22:
score: 0
Wrong Answer
time: 363ms
memory: 71304kb
input:
200000 200000 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 0 0 9 0 10 0 0 0 0 0 13 0 14 0 0 0 16 0 17 0 18 0 19 0 0 0 21 0 22 0 23 0 0 0 0 0 0 0 0 0 28 0 0 0 30 0 31 0 32 0 33 0 34 0 35 0 0 0 0 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 0 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 0 0 59 0 60 0 0 0 0 ...
output:
22432 46052 17444 68789 18109 5870 30967 109395 3294 91576 75155 65043 3007 17824 29172 67569 42104 60169 79239 52762 32527 29078 63908 31551 85805 8848 4540 48908 79576 122635 51073 4419 15232 37151 20241 100118 19478 33634 75043 66160 27978 56059 26747 100983 44152 52519 104178 42562 18576 39534 1...
result:
wrong answer 1st numbers differ - expected: '19141', found: '22432'
Subtask #4:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 310ms
memory: 69764kb
input:
200000 200000 0 200000 1 200000 1 200000 0 200000 0 200000 1 200000 1 200000 1 200000 0 200000 1 200000 0 200000 0 200000 1 200000 0 200000 0 200000 0 200000 0 200000 1 200000 0 200000 0 200000 1 200000 0 200000 1 200000 1 200000 1 200000 1 200000 0 200000 0 200000 1 200000 2 200000 1 200000 2 20000...
output:
54636 16364 50225 36116 47652 22447 111995 104549 126674 62368 19447 92053 80388 9653 69469 24435 38547 11858 1171 81264 70550 54701 12887 3741 29193 26623 102060 75549 515 20084 5042 132989 46796 54961 12052 85968 96225 11666 31965 23363 18421 13285 8448 88323 17067 28729 77724 91867 96842 36159 53...
result:
wrong answer 1st numbers differ - expected: '71224', found: '54636'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%