| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 90208 | jasony123123 | Mostovi (COI14_mostovi) | C++11 | 1090 ms | 142192 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
void io() {
#ifdef LOCAL_PROJECT
freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
/* online submission */
#endif
ios_base::sync_with_stdio(false); cin.tie(NULL);
}
const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/****************************************************************/
const int SZ = 1 << 19;
struct SegmentTree {
set<int> data[SZ * 2];
void update(int p, int val) {
p += SZ;
while (p) {
data[p].insert(val);
p /= 2;
}
}
int query(int node, int nodeLo, int nodeHi, int l, int r, int x, int y) { // is there an element in [l,r] with value between [x,y];
if (nodeLo > r || nodeHi < l) return 0;
if (l <= nodeLo && nodeHi <= r) {
// return 1 = exist elem between x and y
auto itlo = data[node].lower_bound(x);
return itlo != data[node].end() && *itlo <= y;
}
int mid = (nodeLo + nodeHi) / 2;
return query(node * 2, nodeLo, mid, l, r, x, y) || query(node * 2 + 1, mid + 1, nodeHi, l, r, x, y);
}
int query(int l, int r, int x, int y) { // is there an element in [l,r] with value between [x,y]
return query(1, 0, SZ - 1, l, r, x, y);
}
};
int N, M;
v<pair<char, pii>> operations;
set<int> topEnd, botEnd;
set<pii> topBri, botBri;
SegmentTree segTree;
int query1(int A, int B, set<int> &ends) { // A, B same side A<B
return ends.lower_bound(A) == ends.lower_bound(B);
}
int query2(int A, set<int> &endsA, SegmentTree &treeA, int B, set<int> &endsB) { // A, B, different sides
return treeA.query(A, *(endsA.lower_bound(A)), *(--endsB.lower_bound(B)) + 1, B);
}
int query3(int A, int B, set<pii> &briSame, set<int> &endSame, set<int> &endOpp, SegmentTree &treeOpp) { // A, B same side B<A
auto bridgeA = briSame.lower_bound({ A,-1 });
auto compA = endSame.lower_bound(A);
if (*compA < bridgeA->first) return 0;
int C = bridgeA->second;
return query2(C, endOpp, treeOpp, B, endSame);
}
void bridge(int A, int B, SegmentTree &treeA, set<pii> &briA) { // build bridge from A->B
briA.insert({ A,B });
treeA.update(A, B);
}
void block(int B, set<int> &endsB) { // add a new block at B
endsB.insert(B);
}
int transform(int x) {
if (x <= N) return x;
return 2 * N - (x - (N + 1));
}
void init() {
// compress coordinates
v<int> dat;
cin >> N >> M;
FOR(i, 0, M) {
pair<char, pii> op;
cin >> op.first >> op.second.first >> op.second.second;
op.second.first = transform(op.second.first);
op.second.second = transform(op.second.second);
operations.push_back(op);
dat.push_back(op.second.first);
dat.push_back(op.second.second);
}
dat.push_back(0);
dat.push_back(N);
dat.push_back(N + N);
sort(dat.begin(), dat.end());
dat.erase(unique(dat.begin(), dat.end()), dat.end());
for (auto &op : operations) {
op.second.first = lower_bound(all(dat), op.second.first) - dat.begin();
op.second.second = lower_bound(all(dat), op.second.second) - dat.begin();
}
topEnd.insert({ lower_bound(all(dat), 0) - dat.begin() ,lower_bound(all(dat), N) - dat.begin() });
botEnd.insert({ lower_bound(all(dat), N) - dat.begin() , lower_bound(all(dat), N + N) - dat.begin() });
N = lower_bound(all(dat), N) - dat.begin();
}
int main() {
io();
init();
for (auto &op : operations) {
if (op.first == 'A') {
if (op.second.first > op.second.second) swap(op.second.first, op.second.second);
int a = op.second.first, b = op.second.second;
bridge(a, b, segTree, topBri);
bridge(b, a, segTree, botBri);
}
else if (op.first == 'B') {
if (op.second.first > op.second.second) swap(op.second.first, op.second.second);
int b = op.second.first;
if (b <= N)
block(b, topEnd);
else
block(b, botEnd);
}
else {
int res;
int a = op.second.first, b = op.second.second;
int sideA = a <= N, sideB = b <= N; // 1 = top, 0 = bot
if (sideA == sideB && a < b) {
if (sideA == 1)// top, top
res = query1(a, b, topEnd);
else// bot, bot
res = query1(a, b, botEnd);
}
else if (sideA != sideB) {
if (sideA == 1) // top, bot
res = query2(a, topEnd, segTree, b, botEnd);
else // bot, top
res = query2(a, botEnd, segTree, b, topEnd);
}
else { // if (sideA == sideB && b < a)
if (sideA == 1) // top, top
res = query3(a, b, topBri, topEnd, botEnd, segTree);
else // bot
res = query3(a, b, botBri, botEnd, topEnd, segTree);
}
cout << (res == 1 ? "DA\n" : "NE\n");
}
}
return 0;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||