Submission #1692465
Source Code Expand
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
const int INF=1e9;
struct node{
int x,y;
}a[100100],d[100100],h[100100];
bool operator < (const node &A,const node &B){
return A.x>B.x;
}
bool cmpr(const node &A,const node &B){
return A.y<B.y;
}
priority_queue<node> q;
int top,cnt;
int b[100100],g[100100];
int c[100100],f[100100],mp[100100];
int ans;
int main(){
// freopen("F.in","r",stdin);
int n;
scanf("%d",&n);
ans=n;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
swap(a[i].x,a[i].y);
}
for(int i=1;i<=n+1;i++){
scanf("%d",&b[i]);
c[i]=b[i];
}
sort(b+1,b+n+1+1);
int num=unique(b+1,b+n+1+1)-b-1;
for(int i=1;i<=num;i++)
mp[i]=b[i];
for(int i=1;i<=n+1;i++)
c[i]=lower_bound(b+1,b+num+1,c[i])-b;
for(int i=1;i<=n;i++){
a[i].x=lower_bound(b+1,b+num+1,a[i].x)-b;
a[i].y=lower_bound(b+1,b+num+1,a[i].y)-b;
}
memset(b,0,sizeof(b));
for(int i=1;i<=n+1;i++)
b[c[i]]--;
for(int i=1;i<=n;i++){
if(a[i].y<=a[i].x)
b[a[i].x]++;
else
{
b[a[i].y]++;
a[++top]=a[i];
}
}
for(int i=1;i<=num;i++)
b[i]=b[i-1]+b[i];
sort(a+1,a+top+1,cmpr);
int l=top;
top=0;
bool bo=0;
int st=0;
for(int i=num;i>=1;i--)
{
while(l>=1&&a[l].y>i){
q.push(a[l]);
l--;
}
st-=f[i];
for(int j=1;j<(-b[i]-st);j++){
if(q.empty()){
bo=1;
break;
}
d[++top]=q.top();
f[d[top].x-1]++;
q.pop();
st++;
}
if(bo) break;
}
int Q,x,y;
if(bo){
scanf("%d",&Q);
while(Q--)
printf("-1\n");
return 0;
}
memset(f,0,sizeof(f));
for(int i=1;i<=top;i++)
f[d[i].x]++,f[d[i].y]--;
for(int i=1;i<=num;i++)
f[i]=f[i-1]+f[i];
for(int i=1;i<=num;i++)
b[i]=b[i]+f[i];
ans-=top;
top=0;
while(!q.empty()){
a[++top]=q.top();
q.pop();
}
sort(a+1,a+top+1,cmpr);
l=top;
int mn=INF;
for(int i=num;i>=1;i--)
{
while(l>=1&&a[l].y>i){
if(a[l].x<mn) mn=a[l].x;
l--;
}
g[i]=mn;
}
memset(f,0,sizeof(f));
for(int i=1;i<=num;i++){
if(b[i]>=0)
f[i]=f[i-1];
else{
if(g[i]>i) f[i]=-1;
else{
if(f[g[i]-1]==-1) f[i]=-1;
else f[i]=f[g[i]-1]+1;
}
}
}
scanf("%d",&Q);
while(Q--){
scanf("%d%d",&x,&y);
x=lower_bound(mp+1,mp+num+1,x)-mp;
y=lower_bound(mp+1,mp+num+1,y)-mp;
st=-1;
if(x<=num&&f[x-1]>-1&&ans-f[x-1]+1>st) st=ans-f[x-1]+1;
if(y<=num&&f[y-1]>-1&&ans-f[y-1]>st) st=ans-f[y-1];
printf("%d\n",st);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Two Faced Cards |
User |
xzkflowey |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2558 Byte |
Status |
WA |
Exec Time |
154 ms |
Memory |
6004 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:25:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:29:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a[i].x,&a[i].y);
^
./Main.cpp:34:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&b[i]);
^
./Main.cpp:89:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&Q);
^
./Main.cpp:133:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&Q);
^
./Main.cpp:135:22: warning: ignoring r...
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 2000 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_49.txt, subtask_1_50.txt, subtask_1_51.txt, subtask_1_52.txt, subtask_1_53.txt, subtask_1_54.txt, subtask_1_55.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
3 ms |
3196 KB |
sample_02.txt |
AC |
2 ms |
3072 KB |
sample_03.txt |
AC |
2 ms |
3072 KB |
subtask_1_01.txt |
WA |
44 ms |
3200 KB |
subtask_1_02.txt |
AC |
75 ms |
4472 KB |
subtask_1_03.txt |
WA |
23 ms |
2944 KB |
subtask_1_04.txt |
AC |
68 ms |
4596 KB |
subtask_1_05.txt |
AC |
49 ms |
3964 KB |
subtask_1_06.txt |
WA |
105 ms |
4604 KB |
subtask_1_07.txt |
WA |
108 ms |
5364 KB |
subtask_1_08.txt |
WA |
100 ms |
4984 KB |
subtask_1_09.txt |
AC |
98 ms |
4980 KB |
subtask_1_10.txt |
WA |
60 ms |
4216 KB |
subtask_1_11.txt |
WA |
55 ms |
4216 KB |
subtask_1_12.txt |
WA |
52 ms |
4092 KB |
subtask_1_13.txt |
AC |
75 ms |
4472 KB |
subtask_1_14.txt |
WA |
44 ms |
3964 KB |
subtask_1_15.txt |
AC |
58 ms |
3328 KB |
subtask_1_16.txt |
WA |
32 ms |
3584 KB |
subtask_1_17.txt |
AC |
144 ms |
5876 KB |
subtask_1_18.txt |
WA |
35 ms |
3836 KB |
subtask_1_19.txt |
AC |
47 ms |
3456 KB |
subtask_1_20.txt |
WA |
112 ms |
5112 KB |
subtask_1_21.txt |
WA |
78 ms |
3968 KB |
subtask_1_22.txt |
AC |
149 ms |
6004 KB |
subtask_1_23.txt |
WA |
78 ms |
3968 KB |
subtask_1_24.txt |
AC |
149 ms |
6004 KB |
subtask_1_25.txt |
AC |
153 ms |
6004 KB |
subtask_1_26.txt |
WA |
150 ms |
5620 KB |
subtask_1_27.txt |
WA |
145 ms |
5240 KB |
subtask_1_28.txt |
WA |
149 ms |
5624 KB |
subtask_1_29.txt |
AC |
153 ms |
6004 KB |
subtask_1_30.txt |
WA |
151 ms |
5748 KB |
subtask_1_31.txt |
AC |
81 ms |
3968 KB |
subtask_1_32.txt |
WA |
148 ms |
5624 KB |
subtask_1_33.txt |
AC |
154 ms |
6004 KB |
subtask_1_34.txt |
WA |
148 ms |
5496 KB |
subtask_1_35.txt |
AC |
81 ms |
4096 KB |
subtask_1_36.txt |
WA |
148 ms |
5624 KB |
subtask_1_37.txt |
AC |
153 ms |
6004 KB |
subtask_1_38.txt |
WA |
149 ms |
5620 KB |
subtask_1_39.txt |
WA |
148 ms |
5496 KB |
subtask_1_40.txt |
WA |
150 ms |
5624 KB |
subtask_1_41.txt |
WA |
59 ms |
3712 KB |
subtask_1_42.txt |
AC |
97 ms |
4608 KB |
subtask_1_43.txt |
AC |
119 ms |
5236 KB |
subtask_1_44.txt |
WA |
98 ms |
4276 KB |
subtask_1_45.txt |
AC |
57 ms |
3584 KB |
subtask_1_46.txt |
WA |
88 ms |
4096 KB |
subtask_1_47.txt |
AC |
82 ms |
4352 KB |
subtask_1_48.txt |
AC |
101 ms |
5108 KB |
subtask_1_49.txt |
WA |
83 ms |
4352 KB |
subtask_1_50.txt |
WA |
86 ms |
4352 KB |
subtask_1_51.txt |
AC |
2 ms |
3072 KB |
subtask_1_52.txt |
AC |
2 ms |
3072 KB |
subtask_1_53.txt |
AC |
2 ms |
3072 KB |
subtask_1_54.txt |
AC |
2 ms |
3072 KB |
subtask_1_55.txt |
AC |
2 ms |
3072 KB |