Submission #1555053
Source Code Expand
#include <cstdio>
#include <cctype>
#include <algorithm>
namespace Zeonfai
{
inline int getInt()
{
int a = 0, sgn = 1; char c;
while(! isdigit(c = getchar())) if(c == '-') sgn *= -1;
while(isdigit(c)) a = a * 10 + c - '0', c = getchar();
return a * sgn;
}
}
using namespace std;
const int N = (int)2e5;
int n;
int mn[N + 1], mx[N + 1];
struct point
{
int v, pos;
inline int operator <(const point &a) const {return v < a.v;}
}p[N + 1];
struct section
{
int L, R;
inline int operator <(const section &a) const {return R < a.R;}
}sec[N + 1];
struct binaryIndexedTree
{
long long a[N + 2];
inline void modify(int pos, int x)
{
for(int i = pos + 1; i <= n + 1; i += i & - i) a[i] += x;
}
long long query(int pos)
{
long long res = 0;
for(int i = pos + 1; i; i -= i & - i) res += a[i];
return res;
}
inline long long query(int L, int R) {return query(R) - query(L - 1);}
}BIT;
int main()
{
#ifndef ONLINE_JUDGE
freopen("incubator.in", "r", stdin);
freopen("incubator.out", "w", stdout);
#endif
using namespace Zeonfai;
n = getInt();
for(int i = 1; i <= n; ++ i) p[i].pos = getInt(), p[i].v = getInt();
sort(p + 1, p + n + 1);
for(int i = 1; i <= n; ++ i) mx[i] = i == 1 ? p[i].pos : max(mx[i - 1], p[i].pos);
for(int i = n; i; -- i) mn[i] = i == n ? p[i].pos : min(mn[i + 1], p[i].pos);
for(int i = 1; i <= n; ++ i)
{
int L = 1, R = i - 1, pos = i;
while(L <= R) if(mx[L + R >> 1] > p[i].pos) {pos = L + R >> 1; R = (L + R >> 1) - 1;} else L = (L + R >> 1) + 1;
sec[i].L = pos;
L = i + 1; R = n; pos = i;
while(L <= R) if(mn[L + R >> 1] < p[i].pos) {pos = L + R >> 1; L = (L + R >> 1) + 1;} else R = (L + R >> 1) - 1;
sec[i].R = pos;
}
sort(sec + 1, sec + n + 1);
BIT.modify(0, 1);
for(int i = 1; i <= n; ++ i)
BIT.modify(sec[i].R, BIT.query(sec[i].L - 1, sec[i].R));
printf("%lld\n", BIT.query(n, n));
}
Submission Info
Submission Time |
|
Task |
E - Mr.Aoki Incubator |
User |
ZeonfaiHo |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2128 Byte |
Status |
TLE |
Exec Time |
2103 ms |
Memory |
128 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:49:40: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen("incubator.in", "r", stdin);
^
./Main.cpp:50:42: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen("incubator.out", "w", stdout);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, s1.txt, s2.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
TLE |
2103 ms |
128 KB |
02.txt |
TLE |
2103 ms |
128 KB |
03.txt |
TLE |
2103 ms |
128 KB |
04.txt |
TLE |
2103 ms |
128 KB |
05.txt |
TLE |
2103 ms |
128 KB |
06.txt |
TLE |
2103 ms |
128 KB |
07.txt |
TLE |
2103 ms |
128 KB |
08.txt |
TLE |
2103 ms |
128 KB |
09.txt |
TLE |
2103 ms |
128 KB |
10.txt |
TLE |
2103 ms |
128 KB |
11.txt |
TLE |
2103 ms |
128 KB |
12.txt |
TLE |
2103 ms |
128 KB |
13.txt |
TLE |
2103 ms |
128 KB |
14.txt |
TLE |
2103 ms |
128 KB |
15.txt |
TLE |
2103 ms |
128 KB |
16.txt |
TLE |
2103 ms |
128 KB |
17.txt |
TLE |
2103 ms |
128 KB |
18.txt |
TLE |
2103 ms |
128 KB |
19.txt |
TLE |
2103 ms |
128 KB |
20.txt |
TLE |
2103 ms |
128 KB |
21.txt |
TLE |
2103 ms |
128 KB |
22.txt |
TLE |
2103 ms |
128 KB |
23.txt |
TLE |
2103 ms |
128 KB |
24.txt |
TLE |
2103 ms |
128 KB |
25.txt |
TLE |
2103 ms |
128 KB |
26.txt |
TLE |
2103 ms |
128 KB |
27.txt |
TLE |
2103 ms |
128 KB |
28.txt |
TLE |
2103 ms |
128 KB |
29.txt |
TLE |
2103 ms |
128 KB |
30.txt |
TLE |
2103 ms |
128 KB |
31.txt |
TLE |
2103 ms |
128 KB |
32.txt |
TLE |
2103 ms |
128 KB |
33.txt |
TLE |
2103 ms |
128 KB |
34.txt |
TLE |
2103 ms |
128 KB |
s1.txt |
TLE |
2103 ms |
128 KB |
s2.txt |
TLE |
2103 ms |
128 KB |