Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/tree_policy.hpp>
- #include <ext/pb_ds/assoc_container.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- //#pragma comment(linker, "/stack:200000000")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("-O")
- #pragma GCC optimize("-s")
- #pragma GCC optimize("-Os")
- #pragma GCC optimize("-O1")
- #pragma GCC optimize("-O2")
- #pragma GCC optimize("-O3")
- #define ll long long
- #define ld long double
- #define int ll
- #define F first
- #define S second
- #define pb push_back
- #define pf push_front
- #define endl '\n'
- #define TIME 1.0*clock()/CLOCKS_PER_SEC
- #define pii pair<int, int>
- #define Tip pii
- typedef tree< Tip, null_type, less<Tip>, rb_tree_tag, tree_order_statistics_node_update> ord_set;
- #ifdef SashOK
- #else
- #define cerr if(0)cerr
- #endif
- const int inf = 1e9;
- main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- #ifdef SashOK
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- // freopen("INPUT.TXT", "r", stdin);
- // freopen("OUTPUT.TXT", "w", stdout);
- // freopen("forest.in", "r", stdin);
- // freopen("forest.out", "w", stdout);
- #endif
- int n;
- cin >> n;
- vector<pii> m;
- vector<pii> p;
- int mm = 0, pp = 0;
- int ODIN = 0;
- int ans = 0;
- for(int i = 0; i < n; i++)
- {
- int x, t;
- cin >> x >> t;
- if(x == 0 && t != 0)
- {
- ODIN++;
- continue;
- }
- if(x > 0)
- {
- p.pb({x, t});
- }
- else
- {
- m.pb({-x, t});
- }
- // a.pb({x, t});
- }
- sort(m.begin(), m.end());
- sort(p.begin(), p.end());
- int id = 1;
- // ord_set mem;
- // mem.insert({1, 1});
- // mem.insert({2, 2});
- // mem.insert({3, 3});
- // mem.insert({4, 4});
- // cout << mem.order_of_key({2, -1});
- // return 0;
- /// 1)<- 2)->
- // for(auto to:m)cout << to.F << ' ' << to.S << endl;
- // cout << endl;
- // for(auto to:p)cout << to.F << ' ' << to.S << endl;
- ord_set st1;
- for(int i = 0; i < m.size(); i++)
- {
- if(m[i].S > m[i].F)
- {
- st1.insert({m[i].S - m[i].F, id});
- id++;
- }
- }
- // for(auto to:st1)
- // {
- // cout << to.F << ' ';
- // }
- int k1 = 0;
- for(int i = 0; i < p.size(); i++)
- {
- if(p[i].F < p[i].S)
- {
- k1++;
- ans = max(ans, k1 + st1.size() - st1.order_of_key({p[i].F * 2 + 1, -1}));
- }
- }
- /// 1)-> 2)<-
- ord_set st2;
- for(int i = 0; i < p.size(); i++)
- {
- if(p[i].S > p[i].F)
- {
- st2.insert({p[i].S - p[i].F, id});
- id++;
- }
- }
- int k2 = 0;
- for(int i = 0; i < m.size(); i++)
- {
- if(m[i].F < m[i].S)
- {
- k2++;
- ans = max(ans, k2 + st2.size() - st2.order_of_key({m[i].F * 2 + 1, 0}));
- }
- }
- int ansver = ans + ODIN;
- if(ansver > 0 && ansver % 2 == 0)ansver--;
- cout << ansver;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement