oj.uz

Submission #59354

# Submission time Handle Problem Language Result Execution time Memory
59354 2018-07-21T17:32:05 Z Benq trapezoid (balkan11_trapezoid) C++14
100 / 100
 325 ms 36984 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

    
pi comb(pi a, pi b) {  
    if (a.f != b.f) return max(a,b);
    return {a.f,(a.s+b.s)%30013};
} 
    
template<class T, int SZ> struct Seg {
    T seg[2*SZ], MN = {0,0};
    
    Seg() {
        memset(seg,0,sizeof seg);
    }
    
    void upd(int p, T value) {  // set value at position p
        for (seg[p += SZ] = value; p > 1; p >>= 1)
            seg[p>>1] = comb(seg[(p|1)^1],seg[p|1]); // non-commutative operations
    }
    
    void build() {
        F0Rd(i,SZ) seg[i] = comb(seg[2*i],seg[2*i+1]);
    }
    
    T query(int l, int r) {  // sum on interval [l, r]
        T res1 = MN, res2 = MN; r++;
        for (l += SZ, r += SZ; l < r; l >>= 1, r >>= 1) {
            if (l&1) res1 = comb(res1,seg[l++]);
            if (r&1) res2 = comb(seg[--r],res2);
        }
        return comb(res1,res2);
    }
};

Seg<pi,1<<18> S;
int N;
map<int,int> m;
priority_queue<array<int,4>,vector<array<int,4>>,greater<array<int,4>>> p;
pi ans;
vector<array<int,4>> v;

void input() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    m[0] = 1;
    F0R(i,N) {
        int a,b,c,d; cin >> a >> b >> c >> d;
        v.pb({a,b,c,d});
        m[c] = m[d] = 0;
    }
    S.upd(0,{0,1});
    int co = 0;
    for (auto& a: m) a.s = co++;
    for (auto& a: v) {
        a[2] = m[a[2]];
        a[3] = m[a[3]];
    }
}

int main() {
    input();
    sort(all(v));
    for (auto x: v) {
        while (sz(p) && p.top()[0] < x[0]) {
            S.upd(p.top()[1],{p.top()[2],p.top()[3]});
            p.pop();
        }
        pi z = S.query(0,x[2]-1); z.f ++;
        ans = comb(ans,z);
        p.push({x[1],x[3],z.f,z.s});
    }
    cout << ans.f << " " << ans.s;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4472 KB Output is correct
2 Correct 6 ms 4476 KB Output is correct
3 Correct 6 ms 4516 KB Output is correct
4 Correct 9 ms 4784 KB Output is correct
5 Correct 10 ms 5100 KB Output is correct
6 Correct 12 ms 5168 KB Output is correct
7 Correct 12 ms 5372 KB Output is correct
8 Correct 20 ms 5612 KB Output is correct
9 Correct 27 ms 6484 KB Output is correct
10 Correct 62 ms 8116 KB Output is correct
11 Correct 57 ms 9280 KB Output is correct
12 Correct 149 ms 13532 KB Output is correct
13 Correct 163 ms 16220 KB Output is correct
14 Correct 225 ms 19600 KB Output is correct
15 Correct 221 ms 21956 KB Output is correct
16 Correct 325 ms 24852 KB Output is correct
17 Correct 285 ms 27796 KB Output is correct
18 Correct 309 ms 30512 KB Output is correct
19 Correct 310 ms 33752 KB Output is correct
20 Correct 292 ms 36984 KB Output is correct