Submission #1440584
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
int N, M, a[100009], b[100009], c[100009], d[100009], e[100009], v[100009], ans[100009], aib[100009];
vector < int > g[100009], h[100009];
void refresh (int &x)
{
x = lower_bound (c + 1, c + N + 3, x) - c;
}
void U (int pos, int val)
{
while (pos <= N + 1)
aib[pos] += val, pos += pos - (pos & (pos - 1));
}
int Q (int pos)
{
int ans = 0;
while (pos)
ans += aib[pos], pos &= pos - 1;
return ans;
}
multiset < pair < int, int > > used, S;
void useSegm (int i, int j)
{
U (i, +1);
U (j + 1, -1);
used.insert ({i, j});
}
void adSegm (int i, int j)
{
//printf ("[%d, %d]\n", i, j);
g[j].push_back (i);
h[i].push_back (j);
}
int getAns (int i, int j)
{
int currAns = -1;
if (ans[i - 1] != -1) currAns = max (currAns, N + 1 - ans[i - 1]);
if (ans[j - 1] != -1) currAns = max (currAns, N - ans[j - 1]);
return currAns;
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
scanf ("%d", &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]), v[i] = -1;
sort (c + 1, c + N + 2), c[N + 2] = 1e9 + 10;
scanf ("%d", &M);
for (int i=1; i<=M; i++)
scanf ("%d %d", &d[i], &e[i]), refresh (d[i]), refresh (e[i]);
for (int i=1; i<=N; i++)
{
refresh (a[i]), refresh (b[i]), v[a[i]] ++;
if (b[i] < a[i])
adSegm (b[i], a[i] - 1);
}
for (int i=1; i<=N + 1; i++)
v[i] += v[i - 1];
//for (int i=1; i<=N + 1; i++)
// printf ("%d%c", v[i], " \n"[i == N + 1]);
for (int i=N + 1; i>=1; i--)
{
for (auto lft : g[i])
S.insert ({lft, i});
int curr = v[i] + Q(i);
while (curr < -1 && !S.empty ())
{
auto it = S.begin ();
useSegm (it->first, it->second), S.erase (it), ans[0] ++;
curr ++;
}
if (curr < -1)
{
for (int i=1; i<=M; i++)
printf ("-1\n");
return 0;
}
}
S.clear ();
for (int i=1; i<=N + 1; i++)
{
for (auto rgt : h[i])
if (used.find ({i, rgt}) != used.end ()) used.erase (used.find ({i, rgt}));
else S.insert ({rgt, i});
ans[i] = ans[i - 1];
int curr = v[i] + Q(i);
while (curr < 0 && !S.empty ())
{
auto it = S.end (); it --;
useSegm (it->second, it->first), S.erase (it), ans[i] ++;
curr ++;
}
if (curr < 0)
{
for (int j=i; j<=N + 1; j++)
ans[j] = -1;
break;
}
}
for (int i=1; i<=M; i++)
printf ("%d\n", getAns (d[i], e[i]));
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Two Faced Cards |
User |
geniucos |
Language |
C++14 (GCC 5.4.1) |
Score |
2000 |
Code Size |
2686 Byte |
Status |
AC |
Exec Time |
199 ms |
Memory |
19584 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:55:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &N);
^
./Main.cpp:57:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d", &a[i], &b[i]);
^
./Main.cpp:59:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &c[i]), v[i] = -1;
^
./Main.cpp:61:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &M);
^
./Main.cpp:63:66: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d", &d[i], &e[i]), refr...
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 |
66 ms |
10112 KB |
subtask_1_02.txt |
AC |
96 ms |
13312 KB |
subtask_1_03.txt |
AC |
36 ms |
8320 KB |
subtask_1_04.txt |
AC |
100 ms |
14592 KB |
subtask_1_05.txt |
AC |
49 ms |
9216 KB |
subtask_1_06.txt |
AC |
109 ms |
15104 KB |
subtask_1_07.txt |
AC |
87 ms |
13312 KB |
subtask_1_08.txt |
AC |
134 ms |
16896 KB |
subtask_1_09.txt |
AC |
112 ms |
15104 KB |
subtask_1_10.txt |
AC |
61 ms |
13056 KB |
subtask_1_11.txt |
AC |
47 ms |
10112 KB |
subtask_1_12.txt |
AC |
67 ms |
11520 KB |
subtask_1_13.txt |
AC |
81 ms |
12032 KB |
subtask_1_14.txt |
AC |
46 ms |
11392 KB |
subtask_1_15.txt |
AC |
61 ms |
11648 KB |
subtask_1_16.txt |
AC |
37 ms |
8576 KB |
subtask_1_17.txt |
AC |
163 ms |
18176 KB |
subtask_1_18.txt |
AC |
38 ms |
11008 KB |
subtask_1_19.txt |
AC |
86 ms |
11264 KB |
subtask_1_20.txt |
AC |
145 ms |
16768 KB |
subtask_1_21.txt |
AC |
154 ms |
13312 KB |
subtask_1_22.txt |
AC |
198 ms |
19584 KB |
subtask_1_23.txt |
AC |
154 ms |
13312 KB |
subtask_1_24.txt |
AC |
199 ms |
19584 KB |
subtask_1_25.txt |
AC |
170 ms |
18432 KB |
subtask_1_26.txt |
AC |
157 ms |
19200 KB |
subtask_1_27.txt |
AC |
122 ms |
14336 KB |
subtask_1_28.txt |
AC |
182 ms |
18304 KB |
subtask_1_29.txt |
AC |
169 ms |
18432 KB |
subtask_1_30.txt |
AC |
165 ms |
19200 KB |
subtask_1_31.txt |
AC |
124 ms |
14336 KB |
subtask_1_32.txt |
AC |
181 ms |
18304 KB |
subtask_1_33.txt |
AC |
168 ms |
18432 KB |
subtask_1_34.txt |
AC |
153 ms |
19200 KB |
subtask_1_35.txt |
AC |
122 ms |
14336 KB |
subtask_1_36.txt |
AC |
181 ms |
18304 KB |
subtask_1_37.txt |
AC |
170 ms |
18432 KB |
subtask_1_38.txt |
AC |
160 ms |
19200 KB |
subtask_1_39.txt |
AC |
124 ms |
14336 KB |
subtask_1_40.txt |
AC |
198 ms |
18304 KB |
subtask_1_41.txt |
AC |
140 ms |
11904 KB |
subtask_1_42.txt |
AC |
107 ms |
9728 KB |
subtask_1_43.txt |
AC |
149 ms |
14720 KB |
subtask_1_44.txt |
AC |
112 ms |
10240 KB |
subtask_1_45.txt |
AC |
96 ms |
8960 KB |
subtask_1_46.txt |
AC |
130 ms |
11520 KB |
subtask_1_47.txt |
AC |
96 ms |
8704 KB |
subtask_1_48.txt |
AC |
132 ms |
13824 KB |
subtask_1_49.txt |
AC |
103 ms |
9472 KB |
subtask_1_50.txt |
AC |
88 ms |
8576 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 |