QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#316918 | #8176. Next TTPC 3 | ucup-team2894# | WA | 1ms | 5928kb | C++20 | 5.0kb | 2024-01-28 06:42:26 | 2024-01-28 06:42:26 |
Judging History
answer
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())
using namespace std;
#ifdef ONPC
mt19937 rnd(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
.time_since_epoch().count());
#endif
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ld = double;
const int maxn = 4e5 + 100, inf = 1e9 + 100;
struct point {
int x, y;
};
point op[maxn], cl[maxn];
int ans[maxn];
struct Fen {
#define Val int
vector<Val> q;
int n;
vector<int> xs;
void init(vector<int> xs_) {
xs = xs_;
n = xs.size();
q.assign(n, 0);
}
void inc(int i, Val w) {
i = lower_bound(all(xs), i) - xs.begin();
for (; i < n; i = (i | (i + 1)))
q[i] ^= w;
}
Val get(int i) {
i = lower_bound(all(xs), i + 1) - xs.begin();
i--;
Val w = 0;
for (; i >= 0; i = (i & (i + 1)) - 1)
w ^= q[i];
return w;
}
Val get(int l, int r) {
if (l > r)
return 0;
return get(r) - get(l - 1);
}
};
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> op[i].x >> op[i].y;
}
for (int i = 0; i < n; i++) {
cin >> cl[i].x >> cl[i].y;
}
{
struct Event {
int x, y, id;
bool op;
};
vector<Event> que;
for (int i = 0; i < n; i++) {
que.push_back({op[i].x, op[i].y, i, 1});
}
for (int i = 0; i < n; i++) {
que.push_back({cl[i].x, cl[i].y, i, 0});
}
sort(all(que), [&](Event a, Event b) {return make_pair(a.x, a.y) < make_pair(b.x, b.y);});
// (y, x, i)
set<pair<pair<int, int>, int>> g;
for (auto ev : que) {
if (ev.op) {
// open
g.insert({{ev.y, ev.x}, ev.id});
} else {
// close
auto it = g.lower_bound({{ev.y + 1, -inf}, 0});
if (it == g.begin()) {
cout << "No\n";
return;
}
it--;
ans[it->sc] = ev.id;
g.erase(it);
}
}
}
{
struct Event {
bool is_point;
int x, y, w;
int l, r, id, kf;
};
auto get_point = [&](int x, int y, int w) {
Event z;
z.x = x;
z.y = y;
z.w = w;
z.is_point = 1;
return z;
};
auto get_query = [&](int x, int l, int r, int id) {
Event z;
z.x = x;
z.l = l;
z.r = r;
z.id = id;
z.is_point = 0;
return z;
};
vector<Event> que;
for (int i = 0; i < n; i++) {
point a = op[i];
point b = cl[ans[i]];
assert(a.x <= b.x && a.y <= b.y);
{
int X = rnd(), Y = rnd();
que.push_back(get_point(a.x, a.y, X));
que.push_back(get_point(b.x, b.y, X));
que.push_back(get_point(b.x, a.y, Y));
que.push_back(get_point(a.x, b.y, Y));
}
{
que.push_back(get_query(b.x, a.y, b.y, i));
que.push_back(get_query(a.x - 1, a.y, b.y, i));
}
}
sort(all(que), [&](Event a, Event b) {
return make_tuple(a.x, -a.is_point) < make_tuple(b.x, -b.is_point);
});
vector<int> xs;
for (auto ev : que) {
if (ev.is_point) {
xs.push_back(ev.y);
} else {
xs.push_back(ev.l - 1);
xs.push_back(ev.r);
}
}
sort(all(xs));
unique(xs);
Fen f;
f.init(xs);
vector<int> vals(n);
for (auto ev : que) {
if (ev.is_point) {
cerr << "point " << ev.x << ' ' << ev.y << ' ' << ev.w % 10 << '\n';
f.inc(ev.y, ev.w);
} else {
cerr << "query " << ev.x << ' ' << ev.l << ' ' << ev.r << ' ' << ev.id << '\n';
vals[ev.id] ^= f.get(ev.l, ev.r);
}
}
for (int i = 0; i < n; i++)
if (vals[i] != 0) {
cerr << "loose " << i << '\n';
cout << "No\n";
return;
}
}
cout << "Yes\n";
for (int i = 0; i < n; i++)
cout << ans[i] + 1 << '\n';
}
int main() {
#ifdef ONPC
freopen("../a.in", "r", stdin);
// freopen("../a.out", "w", stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed;
cout.precision(20);
solve();
cerr << "\n\nConsumed " << TIME << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5928kb
input:
3 TTPC TLE P AC
output:
Yes 3 2 1
result:
wrong answer 1st words differ - expected: '34', found: 'Yes'