oj.uz

Submission #97517

# Submission time Handle Problem Language Result Execution time Memory
97517 2019-02-16T16:29:26 Z Abelyan trapezoid (balkan11_trapezoid) C++17
0 / 100
 500 ms 63080 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define fr first
#define sc second
#define pir pair<int,int>

const int N=1e5+6;
const int MOD=30013;

bool dzn(char k){
    if (k=='a' || k=='o' || k=='i' || k=='u' || k=='e')return true;
    return false;
}


struct node{
    int sum,mx;
} dp[N],sg[4*N];

node operator +(const node &firstNode,const node &secondNode){
    node c;
    c.sum=(firstNode.sum+secondNode.sum)%MOD;
    c.mx=max(firstNode.mx,secondNode.mx);
    return c;
}

void update(int v,int tl,int tr,int ind,node del){
    if (tl==tr){
        sg[v]=del;
        return;
    }
    int tm=(tl+tr)/2;
    if (ind<=tm){
        update(v+v,tl,tm,ind,del);
    }
    else{
        update(v+v+1,tm+1,tr,ind,del);
    }
    sg[v]=sg[v+v]+sg[v+v+1];
}

node get(int v,int tl,int tr,int l,int r){
    if (l>r) return {0,0};
    if (tl==l && tr==r){
        return sg[v];
    }
    int tm=(tl+tr)/2;
    return get(v+v,tl,tm,l,min(tm,r))+get(v+v+1,tm+1,tr,max(tm+1,l),r);
}


int a[N],b[N],c[N],d[N];
map <int,int> mp;
int ver[N];
vector<int> buck[N];



int main(){
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    set<int> s;
    vector<pair<pir,pir> > v;
    FOR(i,n){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        s.insert(c[i]);
        s.insert(d[i]);
    }
    int qan=0;
    trav (tv,s){
        mp[tv]=qan++;
    }
    FOR(i,n){
        c[i]=mp[c[i]];
        d[i]=mp[d[i]];
        v.push_back({{b[i],a[i]},{c[i],d[i]}});
    }
    sort(v.begin(),v.end());
    vector<int> bin;
    FOR(i,n){
        dp[i]={1,1};
        buck[lower_bound(bin.begin(),bin.end(),v[i].fr.sc)-bin.begin()-1].push_back(i);
        bin.push_back(v[i].fr.fr);
    }
    FOR(i,n){
        update(1,0,qan-1,v[i].sc.sc,dp[i]);
        trav(tv,buck[i]){
            node cur=get(1,0,qan-1,0,v[tv].sc.fr);
            cur.mx++;
            cout<<dp[tv].sum<<" "<<dp[tv].mx<<endl;
            dp[tv]=dp[tv]+cur;
            cout<<dp[tv].sum<<" "<<cur.mx<<endl;
        }
    }
    node ans=get(1,0,qan-1,0,qan-1);
    cout<<ans.mx<<" "<<ans.sum<<endl;
    return 0;
}

/*
8
12 35 57 79 -1 21 -26 18
1
2 8
*/

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB Output isn't correct
2 Incorrect 4 ms 2688 KB Output isn't correct
3 Incorrect 7 ms 2816 KB Output isn't correct
4 Incorrect 10 ms 3136 KB Output isn't correct
5 Incorrect 13 ms 3328 KB Output isn't correct
6 Incorrect 17 ms 3752 KB Output isn't correct
7 Incorrect 25 ms 3960 KB Output isn't correct
8 Incorrect 30 ms 4472 KB Output isn't correct
9 Incorrect 67 ms 6008 KB Output isn't correct
10 Incorrect 143 ms 9584 KB Output isn't correct
11 Incorrect 195 ms 10708 KB Output isn't correct
12 Incorrect 344 ms 19056 KB Output isn't correct
13 Incorrect 447 ms 21996 KB Output isn't correct
14 Runtime error 444 ms 48868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 423 ms 51424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 509 ms 53604 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 557 ms 55356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 640 ms 58728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 468 ms 58600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 653 ms 63080 KB Execution killed with signal 11 (could be triggered by violating memory limits)