이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define all(x) x.begin(), x.end()
using namespace std;
const int maxn = 6e5 + 4;
int n, m, q;
int ans[maxn];
vector<int> f[maxn], fake[maxn];
array<int, 4> qr[maxn], a[maxn];
vector<int> nen;
int comp(int x)
{
return upper_bound(all(nen), x) - nen.begin();
}
void fupd(int x, int y)
{
for (; x > 0; x -= x & -x)
fake[x].emplace_back(y);
}
void fqry(int x, int y)
{
for (; x <= nen.size(); x += x & -x)
fake[x].emplace_back(y);
}
void build()
{
for (int i = 1; i <= nen.size(); i++)
{
if (fake[i].empty()) continue;
sort(all(fake[i]));
fake[i].resize(unique(all(fake[i])) - fake[i].begin());
f[i].resize(fake[i].size() + 1, 0);
}
}
void upd(int x, int y)
{
for (; x > 0; x -= x & -x)
for (int i = lower_bound(all(fake[x]), y) - fake[x].begin() + 1; i > 0; i -= i & -i)
f[x][i]++;
}
int qry(int x, int y)
{
int ans = 0;
for (; x <= nen.size(); x += x & -x)
for (int i = lower_bound(all(fake[x]), y) - fake[x].begin() + 1; i <= fake[x].size(); i += i & -i)
ans += f[x][i];
return ans;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
cin >> a[i][0] >> a[i][1], a[i][2] = a[i][0] + a[i][1];
for (int j = 0; j < 3; j++)
nen.emplace_back(a[i][0]),
nen.emplace_back(a[i][1]),
nen.emplace_back(a[i][2]);
}
for (int i = 1; i <= q; i++)
{
cin >> qr[i][0] >> qr[i][1] >> qr[i][2];
qr[i][3] = i;
for (int j = 0; j < 3; j++)
nen.emplace_back(qr[i][j]);
}
sort(all(nen));
nen.resize(unique(all(nen)) - nen.begin());
sort(all(nen));
nen.resize(unique(all(nen)) - nen.begin());
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < 3; j++)
a[i][j] = comp(a[i][j]);
fupd(a[i][1], a[i][2]);
}
for (int i = 1; i <= q; i++)
{
auto &[u1, u2, v1, v2] = qr[i];
u1 = comp(u1);
u2 = comp(u2);
v1 = comp(v1);
// fqry(u2, v1);
}
build();
sort(a + 1, a + n + 1, greater<>());
sort(qr + 1, qr + q + 1, greater<>());
for (int i = 1, j = 1; i <= q; i++)
{
while (j <= n && a[j][0] >= qr[i][0])
upd(a[j][1], a[j][2]),
j++;
ans[qr[i][3]] = qry(qr[i][1], qr[i][2]);
}
for (int i = 1; i <= q; i++)
cout << ans[i] << "\n";
}
컴파일 시 표준 에러 (stderr) 메시지
examination.cpp: In function 'void fqry(long long int, long long int)':
examination.cpp:27:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for (; x <= nen.size(); x += x & -x)
| ~~^~~~~~~~~~~~~
examination.cpp: In function 'void build()':
examination.cpp:33:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int i = 1; i <= nen.size(); i++)
| ~~^~~~~~~~~~~~~
examination.cpp: In function 'long long int qry(long long int, long long int)':
examination.cpp:52:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (; x <= nen.size(); x += x & -x)
| ~~^~~~~~~~~~~~~
examination.cpp:53:76: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int i = lower_bound(all(fake[x]), y) - fake[x].begin() + 1; i <= fake[x].size(); i += i & -i)
| ~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |