Submission #709088

#TimeUsernameProblemLanguageResultExecution timeMemory
709088swagchickentrapezoid (balkan11_trapezoid)C++14
100 / 100
92 ms9576 KiB
#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 = 30013; #define inf 1e18; #define INF INT_MAX long double PI = 4*atan(1); long double eps = 1e-12; template<class T> class FenwickTree { private: vector<T> ft; public: FenwickTree(int m) { ft.assign(m + 1, {0,0}); } int LSOne(int x) { return x & (-x); } T cmb(T a, T b) { if(a.ff == b.ff) { return {a.ff, (a.ss + b.ss)%MOD}; } else if(a.ff > b.ff) return a; return b; } T RMQ(int j) { // this allows array to be 0 indexed while ft is 1 indexed j++; pii maxv = {0,0}; for(; j > 0; j -= LSOne(j)) { maxv = cmb(maxv, ft[j]); } return maxv; } void update(int i, T v) { i++; for(; i < ft.size(); i += LSOne(i)) { ft[i] = cmb(ft[i], v); } } }; struct QS { int idx, x, y, add; }; 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<int> botv; vector<QS> allq; FOR(i,0,n) { int a,b,c,d; cin >> a >> b >> c >> d; botv.pb(c); botv.pb(d); allq.pb({i, a, c, 0}); allq.pb({i, b, d, 1}); } sort(all(botv)); // botv.erase(unique(all(botv)), botv.end()); for(QS &q : allq) { q.y = lower_bound(all(botv), q.y) - botv.begin(); } sort(all(allq), [&](const QS &a, const QS &b) { return a.x < b.x; }); FenwickTree<pii> st(210000); vector<pii> ans(n+5); for(QS &q : allq) { // cout << q.x << " " << q.y << " " << q.idx << " " << q.add << endl; if(q.add == 0) { pii val = st.RMQ(q.y); if(val.ss == 0) val.ss = 1; ans[q.idx] = {val.ff + 1, val.ss}; } else { st.update(q.y, ans[q.idx]); } } pii res = st.RMQ(201000); cout << res.ff << " " << res.ss << 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(); }

Compilation message (stderr)

trapezoid.cpp: In instantiation of 'void FenwickTree<T>::update(int, T) [with T = std::pair<int, int>]':
trapezoid.cpp:184:34:   required from here
trapezoid.cpp:128:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |             for(; i < ft.size(); i += LSOne(i)) {
      |                   ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...