# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
991089 |
2024-06-01T09:12:25 Z |
megatron10 |
Sails (IOI07_sails) |
C++17 |
|
1000 ms |
4800 KB |
#include <bits/stdc++.h>
#define ull uint64_t
#define ll long long int
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
#define mx5 100005
#define mx52 200005
#define mx6 1000005
#define mod 1000000007
#define smod 998244353
#define nfs \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x)
{
cerr << '{';
__print(x.first);
cerr << ',';
__print(x.second);
cerr << '}';
}
template <typename T>
void __print(const T &x)
{
int f = 0;
cerr << '{';
for (auto &i : x)
cerr << (f++ ? "," : ""), __print(i);
cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
__print(t);
if (sizeof...(v))
cerr << ", ";
_print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...) \
cerr << "[" << #x << "] = ["; \
_print(x)
#else
#define debug(x...)
#endif
template <typename T>
bool MinPlace(T &a, const T &b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T>
bool MaxPlace(T &a, const T &b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
template <typename S, typename T>
ostream &operator<<(ostream &out, const pair<S, T> &p)
{
out << "{" << p.ff << ", " << p.ss << "}";
return out;
}
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v)
{
out << "[";
for (int i = 0; i < (int)v.size(); i++)
{
out << v[i];
if (i != (int)v.size() - 1)
out << ", ";
}
out << "]";
return out;
}
int main()
{
nfs;
int n;
cin >> n;
vector<pi> p(n);
for (int i = 0; i < n; i++)
cin >> p[i].ff >> p[i].ss;
sort(p.begin(), p.end());
set<int> margins{0, 1};
vi rc(mx5, 0);
for (auto [h, k] : p)
{
int low = h - k + 1;
auto itr = margins.lower_bound(low);
if (itr == margins.end())
{
int m = *(--itr);
rc[m]++;
rc[m + k]--;
if (rc[m] == 0)
margins.erase(m);
margins.insert(m + k);
debug(h, k, margins);
continue;
}
int m = *itr, pm = *(--itr);
if (m == low)
{
rc[low]++;
rc[h + 1]--;
if (rc[low] == 0)
margins.erase(low);
if (rc[h + 1] == 0)
margins.erase(h + 1);
else
margins.insert(h + 1);
}
else
{
int down = m - low;
rc[pm]++;
rc[pm + down]--;
rc[m]++;
rc[h + 1]--;
if (rc[pm] == 0)
margins.erase(pm);
margins.insert(pm + down);
if (rc[m] == 0)
margins.erase(m);
if (rc[h + 1] == 0)
margins.erase(h + 1);
else
margins.insert(h + 1);
}
debug(h, k, margins);
}
ll ans = 0;
for (int i = 1; i < mx5; i++)
{
rc[i] += rc[i - 1];
ans += (1ll * rc[i] * (rc[i] - 1)) / 2;
}
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1012 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
856 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
860 KB |
Output is correct |
2 |
Correct |
77 ms |
900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1027 ms |
3664 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1065 ms |
4104 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1096 ms |
3236 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1018 ms |
3664 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1051 ms |
4528 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1061 ms |
3668 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1093 ms |
4800 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |