| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 520408 |
2022-01-29T19:28:22 Z |
Vladth11 |
Sails (IOI07_sails) |
C++14 |
|
206 ms |
7176 KB |
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
const int NMAX = 100001;
const int VMAX = 21;
const int INF = (1LL << 60);
const int MOD = 1000000007;
const int BLOCK = 318;
const int base = 31;
const int nr_of_bits = 17;
int n;
pii v[NMAX];
class AINT {
public:
struct Node {
int l, r;
} aint[NMAX * 4];
int lazy[NMAX * 4];
void init() {
for(int i = 0; i < NMAX * 4; i++) {
aint[i] = {0, 0};
}
}
void propaga(int node, int st, int dr) {
if(st != dr) {
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
aint[node].l += lazy[node];
aint[node].r += lazy[node];
lazy[node] = 0;
}
Node combine(Node a, Node b) {
return {min(a.l, b.l), max(a.r, b.r)}; /// mai putem simplifica
}
int maxim(int node, int st, int dr, int a, int b) {
propaga(node, st, dr);
if(a <= st && dr <= b)
return aint[node].r;
int mid = (st + dr) / 2;
int maxi = 0;
if(a <= mid)
maxi = max(maxi, maxim(node * 2, st, mid, a, b));
if(b > mid)
maxi = max(maxi, maxim(node * 2 + 1, mid + 1, dr, a, b));
return maxi;
}
void update(int node, int st, int dr, int a, int b, int val) {
propaga(node, st, dr);
if(a <= st && dr <= b) {
lazy[node] += val;
return;
}
int mid = (st + dr) / 2;
if(a <= mid)
update(node * 2, st, mid, a, b, val);
if(b > mid)
update(node * 2 + 1, mid + 1, dr, a, b, val);
propaga(node * 2, st, mid);
propaga(node * 2 + 1, mid + 1, dr);
aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}
int findfirst(int node, int st, int dr, int a) {
propaga(node, st, dr);
if(st == dr) {
return st;
}
int mid = (st + dr) / 2;
propaga(node * 2, st, mid);
propaga(node * 2 + 1, mid + 1, dr);
if(aint[node * 2].l <= a) {
return findfirst(node * 2, st, mid, a);
}
return findfirst(node * 2 + 1, mid + 1, dr, a);
}
int findlast(int node, int st, int dr, int a){
propaga(node, st, dr);
if(st == dr){
return st;
}
int mid = (st + dr) / 2;
propaga(node * 2, st, mid);
propaga(node * 2 + 1, mid + 1, dr);
if(aint[node * 2 + 1].r < a){
return findlast(node * 2, st, mid, a);
}
return findlast(node * 2 + 1, mid + 1, dr, a);
}
} st;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int i;
cin >> n;
st.init();
for(i = 1; i <= n; i++) {
cin >> v[i].first >> v[i].second;
}
sort(v + 1, v + n + 1);
for(i = 1; i <= n; i++) {
int k = v[i].second;
int h = v[i].first;
int maxi = st.maxim(1, 1, NMAX - 1, h - k + 1, h);
int first = st.findfirst(1, 1, NMAX - 1, maxi);
int last = st.findlast(1, 1, NMAX - 1, maxi);
last++;
if(last <= h) {
st.update(1, 1, NMAX - 1, last, h, 1);
k -= (h - last + 1);
}
if(k > 0){
st.update(1, 1, NMAX - 1, first, first + k - 1, 1);
}
}
ll total = 0;
for(i = 1; i < NMAX; i++) {
ll cat = st.maxim(1, 1, NMAX - 1, i, i);
if(cat == 0)
break;
total += cat * (cat - 1) / 2;
}
cout << total;
return 0;
}
Compilation message
sails.cpp:12:22: warning: overflow in conversion from 'long long int' to 'int' changes value from '1152921504606846976' to '0' [-Woverflow]
12 | const int INF = (1LL << 60);
| ~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3392 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3396 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3532 KB |
Output is correct |
| 2 |
Correct |
19 ms |
4516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
3972 KB |
Output is correct |
| 2 |
Correct |
63 ms |
4272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
4560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
5196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
160 ms |
6468 KB |
Output is correct |
| 2 |
Correct |
135 ms |
6468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
191 ms |
6844 KB |
Output is correct |
| 2 |
Correct |
94 ms |
6568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
206 ms |
7176 KB |
Output is correct |
| 2 |
Correct |
163 ms |
6364 KB |
Output is correct |
