Submission #1235129

#TimeUsernameProblemLanguageResultExecution timeMemory
1235129vux2codeSails (IOI07_sails)C++20
100 / 100
125 ms3576 KiB
// Src : Vux2Code /* Note : */ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll, ll> pll; #define fi first #define se second #define pusb push_back #define popb pop_back #define pusf push_front #define popf pop_front #define vec3d vector<vector<vector<ll>>> #define vec2d vector<vector<ll>> #define vec1d vector<ll> vec3d set3 (ll x, ll y, ll z, ll val = 0) {return vec3d (x, vec2d (y, vec1d (z, val)));} vec2d set2 (ll x, ll y, ll val = 0) {return vec2d (x, vec1d (y, val));} template<typename T> using rvs_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>; #define forinc(i, a, b) for (ll i = (a); i <= (b); ++i) #define fordec(i, a, b) for (ll i = (a); i >= (b); --i) #define foreach(i, j) for (ll i : (j)) #define all(a) (a).begin (), (a). end () #define uni(a) (a).erase(unique((a).begin(), (a). end ()), (a). end ()) const ll maxN = 1e5 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7; void maxi(ll &x, ll y) { x = max(x, y); } void mini(ll &x, ll y) { x = min(x, y); } /* ---------HASHING-------- */ // const base = 31, mod2 = 1e9 + 9; /* ---------BITMASK-------- */ // ll count(ll x) { return __builtin_popcountll(x); } // ll fst(ll x) { return 63 - __builtin_clzll(x); } // ll last(ll x) { return __builtin_ctzll(x); } // bool bit(ll x, ll y) { return ((x >> y) & 1); } ll t = 1; struct BIT { vector <ll> f; ll n; BIT (ll x) : n (x) ,f (x + 1, 0) {} void update (ll x, ll v) { while (x <= n) { f [x] += v; x += (x & -x); } } ll get (ll x) { ll ans = 0; while (x > 0) { ans += f [x]; x -= (x & -x); } return ans; } }; struct LaziBIT { BIT add, mul; ll n; LaziBIT (ll x) : add (x), mul (x), n (x) {} void update (ll l, ll r, ll v) { mul. update (l, v); mul. update (r + 1, -v); add. update (l, -v * (l - 1)); add. update (r + 1, r * v); } ll get (ll x) { return mul. get (x) * x + add. get (x); } ll getRange (ll x, ll y) { return get (y) - get (x - 1); } }f (maxN); ll finmin (ll l, ll r, ll val) { ll mid, ans = l; while (l <= r) { ll mid = (l + r) >> 1; //cerr << "How the fick : " << l << ' ' << r << ' ' << mid << ' ' << f. getRange (mid, mid) << ' ' << val << '\n'; if (f. getRange (mid, mid) <= val) { ans = mid; r = mid - 1; } else l = mid + 1; } return ans; } ll finmax (ll l, ll r, ll val) { ll mid, ans = r; while (l <= r) { ll mid = (l + r) >> 1; if (f. getRange (mid, mid) >= val) { ans = mid; l = mid + 1; } else r = mid - 1; } return ans; } ll n; pll a [maxN]; void solve() { cin >> n; forinc (i, 1, n) cin >> a [i]. fi >> a [i]. se; sort (a + 1, a + n + 1); //forinc (i, 1, n) cerr << a [i]. fi << ' ' << a [i]. se << '\n'; ll ans = 0; forinc (i, 1, n) { //forinc (j, 1, n) cerr << f. getRange (j, j) << ' '; cerr << '\n'; ll tmp = a [i]. fi - a [i]. se + 1; ans += f. getRange (tmp, a [i]. fi); ll val = f. getRange (tmp, tmp); ll l = finmin (1, a [i]. fi, val); ll r = finmax (1, a [i]. fi, val); f. update (r + 1, a [i]. fi, 1); ll nen = l + (r - tmp); f. update (l, nen, 1); /* cerr << i << ' ' << a [i]. fi << ' ' << a [i]. se << '\n'; cerr << tmp << ' ' << val << '\n'; cerr << l << ' ' << nen << '\n'; cerr << r + 1 << ' ' << a [i]. fi << '\n'; cerr << ans << '\n'; forinc (j, 1, n) cerr << f. getRange (j, j) << ' '; cerr << '\n'; cerr << "\n"; */ } cout << ans << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define TASK "untitled1" if (fopen (TASK".inp", "r")) { freopen (TASK".inp", "r", stdin); freopen (TASK".out", "w", stdout); } //cin >> t; while (t--) solve(); }

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:161:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         freopen (TASK".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sails.cpp:162:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |         freopen (TASK".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...