| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 88081 |
2018-12-03T17:34:46 Z |
MAMBA |
Sunčanje (COCI18_suncanje) |
C++17 |
|
3026 ms |
190244 KB |
#ifdef _MSC_VER
#define __builtin_popcount (int)__popcnt
#define __builtin_popcountll (int)__popcnt64
#define __builtin_clz (int)__lzcnt
#define $ system("pause")
#else
#define $
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> point;
#define MOD ll(1e9 + 7)
#define MAXN int(2e5 + 20)
#define lg 17
#define inf int(2e9 + 100)
#define rep(i, j, k) for (int i = j; i < k; i++)
#define for_all(x) x.begin(), x.end()
#define lid id << 1
#define rid id << 1 | 1
#define lch l, mid, lid
#define rch mid, r, rid
#define pb push_back
#define X first
#define Y second
#define re real()
#define im imag()
template <typename S, typename T>
inline ostream &operator<<(ostream &out, const pair<S, T> &p)
{
return out << "( " << p.X << " , " << p.Y << " )";
}
template <typename S>
inline ostream &operator<<(ostream &out, const vector<S> &p)
{
for (auto &e : p) out << e << ' '; return out;
}
template <typename T, typename S> inline T
smin(T &a, const S &b) { return a > b ? a = b : a; }
template <typename T, typename S> inline T
smax(T &a, const S &b) { return a < b ? a = b : a; }
inline double dot(const point l, const point r) { return l.re * r.re + l.im * r.im; }
inline double cross(const point l, const point r) { return l.re * r.im - l.im * r.re; }
ll po(ll v, ll u) { return u ? (po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD) : 1; }
inline void add(ll &l, const ll &r) { l = (l + r) % MOD; }
ll gcd(ll v, ll u) { return u ? gcd(u, v % u) : v; }
int n, m;
int arr[MAXN], x[MAXN], y[MAXN], a[MAXN], b[MAXN];
bool answer[MAXN];
struct Segment {
set<pii> s;
inline set<pii>::iterator get_itr(int r) {
return s.lower_bound(pii(r, -100));
}
inline set<pii>::iterator get_itl(int l) {
auto itl = s.lower_bound(pii(l, -100));
if (itl != s.begin()) {
auto it2 = itl; it2--;
if ((*it2).Y > l)
itl = it2;
}
return itl;
}
inline bool merge(int l, int r) {
auto itr = get_itr(r);
auto itl = get_itl(l);
if (itl == itr) {
s.insert(pii(l, r));
return false;
}
smin(l, (*itl).X);
itr--;
smax(r, (*itr).Y);
itr++;
s.erase(itl, itr);
s.insert(pii(l, r));
return true;
}
inline bool get(int l, int r) {
return get_itl(l) != get_itr(r);
}
} seg[MAXN * 4], seg2[MAXN * 4];
bool seg_add(int s, int t, int ss, int tt, int l = 0, int r = m, int id = 1) {
if (l >= t || r <= s) return false;
if (l >= s && r <= t) {
bool gholi = seg2[id].merge(ss, tt);
gholi |= seg[id].merge(ss, tt);
return gholi;
}
int mid = l + r >> 1;
seg2[id].merge(ss, tt);
bool gholi = seg_add(s, t, ss, tt, lch);
gholi |= seg_add(s, t, ss, tt, rch);
gholi |= seg[id].get(ss, tt);
return gholi;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
rep(i, 0, n) {
cin >> x[i] >> y[i] >> a[i] >> b[i];
arr[i << 1] = x[i];
arr[i << 1 | 1] = x[i] + a[i] - 1;
}
sort(arr, arr + 2 * n);
m = unique(arr, arr + 2 * n) - arr;
for (int i = n - 1; ~i; i--) {
int l = lower_bound(arr, arr + m, x[i]) - arr;
int r = upper_bound(arr, arr + m, x[i] + a[i] - 1) - arr;
answer[i] = seg_add(l, r, y[i], y[i] + b[i]);
}
rep(i, 0, n)
cout << (answer[i] ? "NE\n" : "DA\n");
$;
return (0);
}
Compilation message
suncanje.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
suncanje.cpp:47:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (auto &e : p) out << e << ' '; return out;
^~~
suncanje.cpp:47:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (auto &e : p) out << e << ' '; return out;
^~~~~~
suncanje.cpp: In function 'bool seg_add(int, int, int, int, int, int, int)':
suncanje.cpp:104:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
78784 KB |
Output is correct |
| 2 |
Correct |
134 ms |
80756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
231 ms |
83988 KB |
Output is correct |
| 2 |
Correct |
871 ms |
116892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
364 ms |
116892 KB |
Output is correct |
| 2 |
Correct |
1319 ms |
131512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
540 ms |
131512 KB |
Output is correct |
| 2 |
Correct |
1156 ms |
131512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1050 ms |
131512 KB |
Output is correct |
| 2 |
Correct |
1321 ms |
135888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1168 ms |
135888 KB |
Output is correct |
| 2 |
Correct |
1567 ms |
138520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1129 ms |
138520 KB |
Output is correct |
| 2 |
Correct |
1183 ms |
138520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1805 ms |
158900 KB |
Output is correct |
| 2 |
Correct |
974 ms |
158900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1934 ms |
158900 KB |
Output is correct |
| 2 |
Correct |
1987 ms |
167608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2052 ms |
167608 KB |
Output is correct |
| 2 |
Correct |
3026 ms |
190244 KB |
Output is correct |
