Submission #1225861
Source Code Expand
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
const int INF = ~0U>>1;
const int maxn = 1E5 + 10;
struct d1{
int l,r,Num; d1(){}
d1(int l,int r,int Num): l(l),r(r),Num(Num){}
bool operator < (const d1 &B) const {return l > B.l;}
};
struct d2{
int l,r,Num; d2(){}
d2(int l,int r,int Num): l(l),r(r),Num(Num){}
bool operator < (const d2 &B) const {return r < B.r;}
};
int n,q,N,A[maxn],B[maxn],C[maxn],D[maxn],E[maxn],Ans[maxn],s[maxn];
bool vis[maxn];
vector <pair<int,int> > L[maxn],R[maxn];
priority_queue <d1> Q1;
priority_queue <d2> Q2;
void Calc()
{
for (int i = 1; i <= n; i++)
for (int j = A[i]; j <= N; j += j&-j) ++s[j];
for (int i = 1; i <= n + 1; i++)
for (int j = C[i]; j <= N; j += j&-j) --s[j];
int Cnt = 0;
for (int i = N; i > 0; i--)
{
int sum = 0;
for (int j = 0; j < R[i].size(); j++)
Q1.push(d1(R[i][j].first,i,R[i][j].second));
for (int j = i; j > 0; j -= j&-j) sum += s[j];
if (sum >= -1) continue; sum = -sum - 1;
for (int l = 0; l < sum; l++)
{
d1 k = Q1.top(); Q1.pop();
++Cnt; vis[k.Num] = 1;
for (int j = k.l; j <= N; j += j&-j) ++s[j];
for (int j = k.r + 1; j <= N; j += j&-j) --s[j];
}
}
Ans[0] = Cnt;
for (int i = 1; i <= N; i++)
{
int sum = 0;
for (int j = 0; j < L[i].size(); j++)
if (!vis[L[i][j].second]) Q2.push(d2(i,L[i][j].first,L[i][j].second));
for (int j = i; j > 0; j -= j&-j) sum += s[j];
if (sum >= 0) {Ans[i] = Cnt; continue;} sum = -sum;
bool pass = 1;
for (int l = 0; l < sum; l++)
{
if (Q2.empty()) {pass = 0; break;}
d2 k = Q2.top(); Q2.pop(); ++Cnt;
if (k.r < i) {pass = 0; break;}
for (int j = k.l; j <= N; j += j&-j) ++s[j];
for (int j = k.r + 1; j <= N; j += j&-j) --s[j];
}
if (!pass)
{
for (int j = i; j <= N; j++) Ans[j] = INF;
break;
}
Ans[i] = Cnt;
}
}
void Pre_Work()
{
for (int i = 1; i <= n; i++)
{
A[i] = lower_bound(D + 1,D + N + 1,A[i]) - D;
B[i] = lower_bound(D + 1,D + N + 1,B[i]) - D;
E[i] = min(A[i],B[i]);
if (B[i] < A[i])
{
L[B[i]].push_back(make_pair(A[i] - 1,i));
R[A[i] - 1].push_back(make_pair(B[i],i));
}
}
for (int i = 1; i <= n + 1; i++)
C[i] = lower_bound(D + 1,D + N + 1,C[i]) - D;
sort(C + 1,C + n + 2); sort(E + 1,E + n + 1);
int now = 1;
for (int i = 1; i <= n; i++)
{
while (now <= n + 1 && C[now] < E[i]) ++now;
if (now == n + 2)
{
while (q--) puts("-1");
exit(0);
}
++now;
}
}
int main()
{
#ifdef DMC
freopen("DMC.txt","r",stdin);
#endif
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d%d",&A[i],&B[i]);
for (int i = 1; i <= n + 1; i++) scanf("%d",&C[i]),D[i] = C[i];
cin >> q; sort(D + 1,D + n + 2); N = 1;
for (int i = 2; i <= n + 1; i++)
if (D[i] != D[i - 1]) D[++N] = D[i];
D[++N] = INF; Pre_Work(); Calc();
while (q--)
{
int X,Y; scanf("%d%d",&X,&Y);
X = lower_bound(D + 1,D + N + 1,X) - D;
Y = lower_bound(D + 1,D + N + 1,Y) - D;
int now = max(n + 1 - Ans[X - 1],n - Ans[Y - 1]);
printf("%d\n",now < 0 ? -1 : now);
}
return 0;
}
Submission Info
Submission Time
2017-04-16 18:27:22+0900
Task
F - Two Faced Cards
User
Charming_Chen
Language
C++14 (GCC 5.4.1)
Score
2000
Code Size
3326 Byte
Status
AC
Exec Time
177 ms
Memory
16500 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:121:56: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= n; i++) scanf("%d%d",&A[i],&B[i]);
^
./Main.cpp:122:64: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= n + 1; i++) scanf("%d",&C[i]),D[i] = C[i];
^
./Main.cpp:129:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int X,Y; scanf("%d%d",&X,&Y);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
2000 / 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
6400 KB
sample_02.txt
AC
3 ms
6400 KB
sample_03.txt
AC
3 ms
6400 KB
subtask_1_01.txt
AC
69 ms
9468 KB
subtask_1_02.txt
AC
85 ms
11384 KB
subtask_1_03.txt
AC
38 ms
8064 KB
subtask_1_04.txt
AC
82 ms
13176 KB
subtask_1_05.txt
AC
50 ms
8700 KB
subtask_1_06.txt
AC
119 ms
12408 KB
subtask_1_07.txt
AC
101 ms
13440 KB
subtask_1_08.txt
AC
128 ms
13564 KB
subtask_1_09.txt
AC
112 ms
14452 KB
subtask_1_10.txt
AC
70 ms
11260 KB
subtask_1_11.txt
AC
49 ms
9984 KB
subtask_1_12.txt
AC
64 ms
9852 KB
subtask_1_13.txt
AC
84 ms
11000 KB
subtask_1_14.txt
AC
55 ms
10232 KB
subtask_1_15.txt
AC
79 ms
11776 KB
subtask_1_16.txt
AC
37 ms
7872 KB
subtask_1_17.txt
AC
173 ms
16372 KB
subtask_1_18.txt
AC
43 ms
10108 KB
subtask_1_19.txt
AC
59 ms
10880 KB
subtask_1_20.txt
AC
138 ms
13304 KB
subtask_1_21.txt
AC
161 ms
12152 KB
subtask_1_22.txt
AC
171 ms
15860 KB
subtask_1_23.txt
AC
160 ms
12024 KB
subtask_1_24.txt
AC
170 ms
15860 KB
subtask_1_25.txt
AC
172 ms
16500 KB
subtask_1_26.txt
AC
172 ms
15476 KB
subtask_1_27.txt
AC
101 ms
14080 KB
subtask_1_28.txt
AC
175 ms
14200 KB
subtask_1_29.txt
AC
175 ms
16500 KB
subtask_1_30.txt
AC
168 ms
15476 KB
subtask_1_31.txt
AC
102 ms
14080 KB
subtask_1_32.txt
AC
174 ms
14200 KB
subtask_1_33.txt
AC
177 ms
16500 KB
subtask_1_34.txt
AC
171 ms
15352 KB
subtask_1_35.txt
AC
103 ms
14080 KB
subtask_1_36.txt
AC
174 ms
14200 KB
subtask_1_37.txt
AC
174 ms
16500 KB
subtask_1_38.txt
AC
169 ms
15352 KB
subtask_1_39.txt
AC
101 ms
14080 KB
subtask_1_40.txt
AC
175 ms
14200 KB
subtask_1_41.txt
AC
120 ms
11128 KB
subtask_1_42.txt
AC
114 ms
9276 KB
subtask_1_43.txt
AC
128 ms
13940 KB
subtask_1_44.txt
AC
115 ms
9280 KB
subtask_1_45.txt
AC
73 ms
8960 KB
subtask_1_46.txt
AC
100 ms
10872 KB
subtask_1_47.txt
AC
93 ms
8448 KB
subtask_1_48.txt
AC
103 ms
13304 KB
subtask_1_49.txt
AC
95 ms
8832 KB
subtask_1_50.txt
AC
59 ms
8448 KB
subtask_1_51.txt
AC
3 ms
6400 KB
subtask_1_52.txt
AC
3 ms
6400 KB
subtask_1_53.txt
AC
3 ms
6400 KB
subtask_1_54.txt
AC
3 ms
6400 KB
subtask_1_55.txt
AC
3 ms
6400 KB