oj.uz

Submission #417711

# Submission time Handle Problem Language Result Execution time Memory
417711 2021-06-04T07:43:02 Z MarcoMeijer trapezoid (balkan11_trapezoid) C++14
100 / 100
 229 ms 49468 KB 
#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
// dp
template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;}
template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;}
 
void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}
 
 
//===================//
//   begin program   //
//===================//
 
const int MX = 5e5;
const int N = (1<<20);
const int MOD = 30013;

int n;
int a[MX], b[MX], c[MX], d[MX];

// fenwick tree
int FT[MX];
void addFT(int i, int value) {
    for(i++; i<MX; i+=i&-i) FT[i] = max(FT[i],value);
}
int getFT(int i) {
    int ans = 0;
    for(i++; i; i-=i&-i) ans = max(ans, FT[i]);
    return ans;
}
int SM[MX];
void addSM(int i, int value) {
    for(i++; i<MX; i+=i&-i) SM[i] = (SM[i]+value)%MOD;
}
int getSM(int i) {
    int ans = 0;
    for(i++; i; i-=i&-i) ans = (ans+SM[i])%MOD;
    return ans;
}

// lis
int lis[MX];
vi atA[MX], atB[MX];
vi layer[MX];
int dp[MX];

void program() {
    IN(n);
    RE(i,n) IN(a[i],b[i],c[i],d[i]);

    // coordinate compression
    vi difx;
    RE(i,n) difx.pb(a[i]), difx.pb(b[i]), difx.pb(c[i]), difx.pb(d[i]);
    sort(all(difx));
    RE(i,n) {
        a[i] = lower_bound(all(difx),a[i]) - difx.begin();
        b[i] = lower_bound(all(difx),b[i]) - difx.begin();
        c[i] = lower_bound(all(difx),c[i]) - difx.begin();
        d[i] = lower_bound(all(difx),d[i]) - difx.begin();
    }

    // getting lis
    RE(i,n) atA[a[i]].pb(i);
    RE(i,n) atB[b[i]].pb(i);
    RE(i,n*4) {
        FOR(j,atA[i])
            lis[j] = getFT(c[j]-1) + 1;
        FOR(j,atB[i])
            addFT(d[j], lis[j]);
    }

    // getting dp
    RE(i,n) layer[lis[i]].pb(i);
    RE1(i,n) {
        priority_queue<iii,viii,greater<iii>> pq;
        FOR(j,layer[i-1])
            pq.push({b[j],2,j});
        FOR(j,layer[i])
            pq.push({a[j],1,j});
        while(!pq.empty()) {
            iii p = pq.top(); pq.pop();
            int x, t, j;
            tie(x,t,j) = p;
            if(t == 1) {
                dp[j] = getSM(c[j]-1);
                if(i == 1)
                    dp[j] = 1;
            }
            if(t == 2)
                addSM(d[j], dp[j]);
        }
        FOR(j,layer[i-1])
            addSM(d[j],-dp[j]);
    }

    int ans=0, ans2=0;
    RE(i,n) ans = max(ans,lis[i]);
    RE(i,n) if(lis[i] == ans) ans2=(ans2+dp[i])%MOD;
    OUTLS(ans,ans2);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35576 KB Output is correct
2 Correct 24 ms 35676 KB Output is correct
3 Correct 26 ms 35708 KB Output is correct
4 Correct 25 ms 35668 KB Output is correct
5 Correct 28 ms 35916 KB Output is correct
6 Correct 32 ms 36012 KB Output is correct
7 Correct 35 ms 36172 KB Output is correct
8 Correct 33 ms 36300 KB Output is correct
9 Correct 42 ms 36948 KB Output is correct
10 Correct 59 ms 38460 KB Output is correct
11 Correct 71 ms 39060 KB Output is correct
12 Correct 119 ms 42216 KB Output is correct
13 Correct 147 ms 43932 KB Output is correct
14 Correct 167 ms 45504 KB Output is correct
15 Correct 185 ms 46000 KB Output is correct
16 Correct 210 ms 46932 KB Output is correct
17 Correct 203 ms 47668 KB Output is correct
18 Correct 202 ms 48084 KB Output is correct
19 Correct 215 ms 48624 KB Output is correct
20 Correct 229 ms 49468 KB Output is correct