| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 520410 |
2022-01-29T19:31:27 Z |
Vladth11 |
Sails (IOI07_sails) |
C++14 |
|
210 ms |
6076 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; /// l e minimul si r maximul
} 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 {b.l, a.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 |
3404 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 |
2 ms |
3404 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 |
3 ms |
3404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3532 KB |
Output is correct |
| 2 |
Correct |
13 ms |
4428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
3892 KB |
Output is correct |
| 2 |
Correct |
54 ms |
3988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
4260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
4684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
5720 KB |
Output is correct |
| 2 |
Correct |
119 ms |
5632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
151 ms |
5772 KB |
Output is correct |
| 2 |
Correct |
77 ms |
5768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
210 ms |
6076 KB |
Output is correct |
| 2 |
Correct |
126 ms |
5244 KB |
Output is correct |
