Submission #119293

#TimeUsernameProblemLanguageResultExecution timeMemory
119293eriksuenderhaufSails (IOI07_sails)C++11
100 / 100
622 ms6276 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define mem(a,v) memset((a), (v), sizeof (a)) #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%lld", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%lld\n", (n)) #define pii pair<int, int> #define pil pair<int, long long> #define pll pair<long long, long long> #define vii vector<pii> #define vil vector<pil> #define vll vector<pll> #define vi vector<int> #define vl vector<long long> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAXN = 1e5 + 5; const double eps = 1e-9; struct node { int mi, indlo, indhi; // minimimum value + leftmost/rightmost index != 0 int len, cnt; // interval length + number of zeros } seg[MAXN*4]; void merge(node &a, node &b, node &c) { a.len = b.len + c.len; a.mi = min(b.mi, c.mi); if (b.len != b.cnt) a.indlo = b.indlo; else a.indlo = c.indlo; if (c.len != c.cnt) a.indhi = c.indhi; else a.indhi = b.indhi; a.cnt = b.cnt + c.cnt; } void build(int l, int r, int k) { if (l == r) { seg[k] = {0, MAXN, -1, 1, 1}; if (l == 0 || l == MAXN-1) seg[k] = {1, l, l, 1, 0}; return; } int m = (l+r) / 2; build(l, m, k*2); build(m+1, r, k*2+1); merge(seg[k], seg[k*2], seg[k*2+1]); } void upd(int l, int r, int k, int a, int v) { if (r < a || a < l) return; if (a <= l && r <= a) { seg[k].mi += v; if (seg[k].mi != 0) { seg[k].indlo = l; seg[k].indhi = l; seg[k].cnt = 0; } else { seg[k].indlo = MAXN; seg[k].indhi = -1; seg[k].cnt = 1; } return; } int m = (l+r) / 2; upd(l, m, k*2, a, v); upd(m+1, r, k*2+1, a, v); merge(seg[k], seg[k*2], seg[k*2+1]); } int qry(int l, int r, int k, int a) { if (r < a || a < l) return 0; if (a <= l && r <= a) return seg[k].mi; int m = (l+r) / 2; return qry(l, m, k*2, a) + qry(m+1, r, k*2+1, a); } pii search(int l, int r, int k, int a, int b) { if (r < a || b < l) return mp(MAXN, 0); if (a <= l && r <= b) return mp(seg[k].indlo, 0); int m = (l+r) / 2; pii ql = search(l, m, k*2, a, b); pii qr = search(m+1, r, k*2+1, a, b); if (seg[k*2].cnt != seg[k*2].len && seg[k*2].indhi < a) ql.se = max(ql.se, seg[k*2].indhi); if (qr.se < a) ql.se = max(ql.se, qr.se); ql.fi = min(ql.fi, qr.fi); if (ql.fi == a) ql.se = a; return ql; } pii a[MAXN]; int main() { int n; ni(n); for (int i = 0; i < n; i++) { int h, k; scanf("%d %d", &h, &k); a[i] = mp(h, k); } sort(a, a + n); build(0, MAXN-1, 1); for (int i = 0; i < n; i++) { int h, k; tie(h, k) = a[i]; int lo = h-k+1, hi = h, ind = 0; int len = k; while (lo <= hi) { int mi = (lo+hi) / 2; pii tmp = search(0, MAXN-1, 1, mi, h); if (h - tmp.se + 1 > k) lo = mi + 1; else hi = min(tmp.se, mi-1), ind = mi; } if (ind != 0) { upd(0, MAXN-1, 1, ind, 1); upd(0, MAXN-1, 1, h+1, -1); len -= h - ind + 1; } if (len != 0) { pii tmp = search(0, MAXN-1, 1, h-k+1, h); if (tmp.se == 0) tmp.se = 1; upd(0, MAXN-1, 1, tmp.se, 1); upd(0, MAXN-1, 1, tmp.se+len, -1); } } ll ans = 0, cur = 0; for (int i = 1; i < MAXN; i++) { ll val = qry(0,MAXN-1,1,i); cur += val; ans += ((cur-1)*cur) / 2ll; } prl(ans); return 0; }

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:9:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
sails.cpp:117:2: note: in expansion of macro 'ni'
  ni(n);
  ^~
sails.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &h, &k);
   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...