#include <bits/stdc++.h>
using namespace std;
#define LSOne(S) ((S) & (-S))
class FenwickTree
{
private:
vector<int> ft, ft2;
public:
FenwickTree(int x)
{
ft.assign(x + 1, 0);
ft2.assign(x + 1, 0);
}
int rsq(int j)
{
int sum = 0;
for (; j; j -= LSOne(j))
{
sum += ft[j];
reset(j);
}
return sum;
}
int rsq2(int j)
{
int sum = 0;
for (; j; j -= LSOne(j))
{
sum += ft2[j];
}
return sum;
}
int rsq(int i, int j) { return rsq(j) - rsq(i - 1); }
int rsq2(int i, int j) { return rsq2(j) - rsq2(i - 1); }
void update(int i, int v)
{
for (; i < (int)ft.size(); i += LSOne(i))
{
ft[i] += v;
}
}
void update2(int i, int v)
{
for (; i < (int)ft2.size(); i += LSOne(i))
{
ft2[i] += v;
}
}
void reset(int x)
{
if (ft[x] == 0)
return;
if (x % 2 == 1)
update2(x, ft[x]);
int re = x - 1;
int notre = ~re;
int ctz = __builtin_ctz(notre);
for (int i = 0; i < ctz; i++, re -= LSOne(re))
reset(re);
}
};
int main()
{
int N;
cin >> N;
FenwickTree FT(2 * N);
FenwickTree Counted(2 * N);
vector<pair<int, int>> Tab(N);
vector<int> fin(N);
for (int i = 0; i < N; i++)
{
int temp;
cin >> temp;
cin >> fin[i];
Tab[i] = {temp, fin[i]};
}
sort(Tab.begin(), Tab.end());
sort(fin.begin(), fin.end());
int buff1 = 0, buff2 = 0, pos = 0;
for (int i = 0; i <= 2 * N; i++)
{
if (i == Tab[buff1].first)
{
pos++;
int moinsmoins = FT.rsq2(Tab[buff1].first, Tab[buff1].second);
int moins = FT.rsq(Tab[buff1].first, Tab[buff1].second);
if (moinsmoins)
{
moins -= moinsmoins;
moins++;
}
FT.update(Tab[buff1].second, 1);
pos -= moins;
buff1++;
}
if (pos == 0)
break;
}
long long ans = 1;
for (int i = 0; i < pos; i++)
{
ans *= 2;
ans = ans % 1000000007;
}
if (ans == 1)
cout << 0;
else
cout << ans;
}
Compilation message
port_facility.cpp: In function 'int main()':
port_facility.cpp:82:20: warning: unused variable 'buff2' [-Wunused-variable]
82 | int buff1 = 0, buff2 = 0, pos = 0;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
