| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 711005 |
2023-03-16T07:07:33 Z |
swagchicken |
Sails (IOI07_sails) |
C++14 |
|
301 ms |
14776 KB |
#include <iostream>
#include <tuple>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cctype>
#include <climits>
#include <chrono>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
template <typename T>
void pr(vector<T> &v) {
FOR(i, 0, sz(v)) cout << v[i] << " ";
cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
cin >> x;
}
template <typename T>
void re(vector<T> &a) {
FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
re(first);
re(rest...);
}
template <typename T>
void pr(T x) {
cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
cout << first << " ";
pr(rest...);
cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
const ll MOD = 1000000007;
#define inf 1e18;
#define INF INT_MAX
long double PI = 4*atan(1);
long double eps = 1e-12;
template<class T>
class LazySegmentTree {
private:
int n;
vector<T> A, stsum, stmin, stmax, lazy;
T ld = 0; // lazy default value, -1 usually, but customize
int l(int p) { return 2*p; }
int r(int p) { return 2*p+1; }
void propagate(int p, int L, int R) {
if (lazy[p] != ld) { // has a lazy flag
stsum[p] += (R - L + 1) * lazy[p];
stmin[p] += lazy[p];
stmax[p] += lazy[p];
if (L != R) { // not a leaf
lazy[l(p)] += lazy[p];
lazy[r(p)] += lazy[p]; // propagate downwards
}
lazy[p] = ld; // erase lazy flag
}
}
T query(int p, int L, int R, int ql, int qr) {
propagate(p, L, R); // lazy propagation
if (qr < L || R < ql) return 0;
if ((ql <= L) && (R <= qr)) return stsum[p];
int m = (L+R)/2;
return query(l(p), L , m, ql, qr) + query(r(p), m+1, R, ql, qr);
}
T query_lft(int p, int L, int R, T val) {
propagate(p, L, R); // lazy propagation
if(stmin[p] > val) return 1e9;
if(L == R) {
if(stmin[p] == val) return L;
return 1e9;
}
int m = (L+R)/2;
int idx1 = query_lft(l(p), L , m, val);
if(idx1 == 1e9) {
idx1 = query_lft(r(p), m+1, R, val);
}
return idx1;
}
T query_rgt(int p, int L, int R, T val) {
propagate(p, L, R); // lazy propagation
if(stmax[p] < val) return -1e9;
if(L == R) {
if(stmax[p] == val) return L;
return -1e9;
}
int m = (L+R)/2;
int idx1 = query_rgt(r(p), m+1, R, val);
if(idx1 == -1e9) {
idx1 = query_rgt(l(p), L, m, val);
}
return idx1;
}
void update(int p, int L, int R, int ul, int ur, T val) {
propagate(p, L, R); // lazy propagation
if(ur < L || R < ul) return;
if ((ul <= L) && (R <= ur)) {
lazy[p] += val;
propagate(p, L, R); // lazy propagation
}
else {
int m = (L+R)/2;
update(l(p), L , m, ul, ur, val);
update(r(p), m+1, R, ul, ur, val);
stsum[p] = stsum[l(p)] + stsum[r(p)];
stmin[p] = min(stmin[l(p)], stmin[r(p)]);
stmax[p] = max(stmax[l(p)], stmax[r(p)]);
}
}
public:
LazySegmentTree(int sz) : n(sz), stsum(4*n), stmin(4*n), stmax(4*n){
lazy.resize(4*n, ld);
}
void update(int i, int j, T val) { update(1, 0, n-1, i, j, val); }
T query(int i, int j) { return query(1, 0, n-1, i, j); }
T query_lft(T val) { return query_lft(1, 0, n-1, val); }
T query_rgt(T val) { return query_rgt(1, 0, n-1, val); }
};
int main() {
//auto start = chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);cin.tie(0);
//ofstream cout("output.txt");
//ifstream cin("input.txt");
#ifdef DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n; cin >> n;
vector<pii> masts(n);
FOR(i,0,n) cin >> masts[i].ff >> masts[i].ss;
sort(all(masts));
LazySegmentTree<ll> st(100010);
ll ans = 0;
// vi slow(1000);
// ll ansslow = 0;
FOR(i,0,n) {
// cout << masts[i].ff << " " << masts[i].ss << endl;
// FOR(j,masts[i].ff - masts[i].ss, masts[i].ff) {
// ansslow += slow[j];
// slow[j]++;
// }
// sort(slow.begin(), slow.begin() + masts[i].ff, greater<int>());
int rgt = masts[i].ff - 1;
int lft = rgt - masts[i].ss + 1;
ll tot = st.query(lft, rgt);
ans += tot;
// cout << ans << " " << ansslow << endl;
// cout << "**" << endl;
ll val = st.query(lft, lft);
int seglft = st.query_lft(val);
int segrgt = st.query_rgt(val);
int len1 = segrgt - lft + 1;
// cout << lft << " " << rgt << endl;
// cout << seglft << " " << segrgt << endl;
// cout << val << endl;
if(val == 0) {
len1 = masts[i].ss;
}
// cout << seglft << " " << seglft + len1 -1 << endl;
// cout << segrgt + 1 << " " << segrgt + masts[i].ss - len1 << endl;
// FOR(j,0,masts[i].ff) {
// cout << slow[j] << " ";
// }
// cout << endl;
st.update(seglft, seglft + len1 - 1, 1);
masts[i].ss -= len1;
if(masts[i].ss > 0) {
st.update(segrgt + 1, masts[i].ff - 1, 1);
}
// FOR(j,0,masts[i].ff) {
// cout <<st.query(j,j) << " ";
// }
// cout << endl;
// cout << "----" << endl;
}
cout << ans << endl;
//auto stop = chrono::high_resolution_clock::now();
//auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
//cout << duration.count() << endl;
//cin.close();
//cout.close();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
5 ms |
12756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
8 ms |
12756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
13012 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
12872 KB |
Output is correct |
| 2 |
Correct |
87 ms |
13280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
13428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
13788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
280 ms |
14324 KB |
Output is correct |
| 2 |
Correct |
208 ms |
14356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
281 ms |
14712 KB |
Output is correct |
| 2 |
Correct |
107 ms |
14156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
301 ms |
14776 KB |
Output is correct |
| 2 |
Correct |
172 ms |
14668 KB |
Output is correct |
