oj.uz

Submission #925162

# Submission time Handle Problem Language Result Execution time Memory
925162 2024-02-10T22:20:53 Z idiotcomputer trapezoid (balkan11_trapezoid) C++11
100 / 100
 171 ms 60692 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pii pair<ll,ll>
#define f first 
#define s second

#define FOR(i, a,b) for(i = a; i < b; i++)
#define ROF(i, b,a) for(i = b-1; i >= a; i--)

const int mxN = 4*1e5;
int n;

ll mod = 30013;

pii stree[4*mxN+1][2];

pii comp(pii a, pii b){
    if (a.f == b.f){
        return {a.f, (a.s+b.s)%mod};
    } else {
        if (a.f < b.f){
            return b;
        }  
        return a;
    }
}

void upd(int t, pii v, bool w, int l = 0, int r = 4*n-1, int idx = 0){
    if (l > t || r < t){
        return;
    }
    if (l == r){
        stree[idx][w] = v;
        return;
    }
    int m = (l+r)/2;
    upd(t,v,w,l,m,2*idx+1);
    upd(t,v,w,m+1,r,2*idx+2);
    stree[idx][w] = comp(stree[2*idx+1][w],stree[2*idx+2][w]);
    return;
}

pii query(int tl, int tr, bool w, int l = 0, int r = 4*n-1, int idx = 0){
    if (l > tr || r < tl){
        return {0,0};
    }
    
    if (l >= tl && r <= tr){
        return stree[idx][w];
    }
 
    int m = (l+r)/2;
    return comp(query(tl,tr,w,l,m,2*idx+1),query(tl,tr,w,m+1,r,2*idx+2));
}

bool c2(pii &a, pii &b){
    return a.f < b.f;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int i,j;
    FOR (i,0,4*mxN+1){
        stree[i][0] = {0,0};
        stree[i][1] = {0,0};
    }
    
    cin >> n;
    
    vector<pii> p(4*n);
    int vals[n][4];
    FOR(i,0,n){
        cin >> p[4*i].f >> p[4*i+1].f >> p[4*i+2].f >> p[4*i+3].f;
    }
    FOR (i,0,4*n) p[i].s = i;
    sort(p.begin(),p.end(),c2);
    
    int nv = 0;
    int last;
    FOR(i,0,4*n){
        last = p[i].f;
        FOR(j,i,4*n){
            if (p[j].f == last){
                vals[p[j].s/4][p[j].s%4] = nv;
                p[j].f = nv;
            } else {
                break;
            }
        }
        i = j-1;
        nv++;
    }

    pii res[n];
    FOR (i,0,n) res[i] = {1,1};
    
    int cnt[n][2];
    memset(cnt,0,sizeof(cnt));
    
    int idx;
    pii temp;
    FOR (i,0,4*n){
        idx = p[i].s / 4;
        if (cnt[idx][0] == 0 && cnt[idx][1] == 0){
            if (p[i].s%4 < 2){
                temp = query(0,vals[idx][2],1);
                res[idx] = comp(res[idx],{temp.f+1,temp.s});
            } else {
                temp = query(0,vals[idx][0],0);
                res[idx] = comp(res[idx],{temp.f+1,temp.s});   
            }
        }
        
        if (p[i].s%4 < 2){
            cnt[idx][0]++;
            if (cnt[idx][0] == 2){
                upd(vals[idx][3],res[idx],1);
            } 
        } else {
            cnt[idx][1]++;
            if (cnt[idx][1] == 2){
                upd(vals[idx][1],res[idx],0);
            }
        }
    }
    pii tot = {0,0};
    FOR (i,0,n){
        tot = comp(tot, res[i]);
    }
    cout << tot.f << " " << tot.s << '\n';
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 50520 KB Output is correct
2 Correct 8 ms 50524 KB Output is correct
3 Correct 8 ms 50524 KB Output is correct
4 Correct 8 ms 50596 KB Output is correct
5 Correct 10 ms 50572 KB Output is correct
6 Correct 11 ms 50776 KB Output is correct
7 Correct 12 ms 50780 KB Output is correct
8 Correct 14 ms 51032 KB Output is correct
9 Correct 21 ms 51548 KB Output is correct
10 Correct 30 ms 52572 KB Output is correct
11 Correct 42 ms 53080 KB Output is correct
12 Correct 85 ms 55496 KB Output is correct
13 Correct 99 ms 56404 KB Output is correct
14 Correct 120 ms 57428 KB Output is correct
15 Correct 130 ms 57936 KB Output is correct
16 Correct 140 ms 58616 KB Output is correct
17 Correct 152 ms 59224 KB Output is correct
18 Correct 114 ms 59472 KB Output is correct
19 Correct 157 ms 59988 KB Output is correct
20 Correct 171 ms 60692 KB Output is correct