답안 #925161

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925161 2024-02-10T22:20:21 Z idiotcomputer 사다리꼴 (balkan11_trapezoid) C++11
100 / 100
171 ms 63384 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){
    /*    if (tr == 18){
            cout << l << "-" << r << " " << stree[idx][w].f << "," << stree[idx][w].s << '\n';
        }*/
        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;
     //   cout << i << "," << last << " ";
        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++;
    }
  //  cout << '\n';
    
    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;
        //cout << idx << " " << p[i].f << ' ' << p[i].s << '\n';
        if (cnt[idx][0] == 0 && cnt[idx][1] == 0){
            if (p[i].s%4 < 2){
                temp = query(0,vals[idx][2],1);
             //   cout << temp.f << "," << temp.s << '\n';
                res[idx] = comp(res[idx],{temp.f+1,temp.s});
            } else {
                temp = query(0,vals[idx][0],0);
             //   cout << temp.f << "," << temp.s << '\n';
                res[idx] = comp(res[idx],{temp.f+1,temp.s});   
            }
        }
        
        if (p[i].s%4 < 2){
            cnt[idx][0]++;
            if (cnt[idx][0] == 2){
             //   cout << res[idx].f << "\n";
                upd(vals[idx][3],res[idx],1);
            } 
        } else {
            cnt[idx][1]++;
            if (cnt[idx][1] == 2){
                //cout << res[idx].f << '\n';
                upd(vals[idx][1],res[idx],0);
            }
        }
    }
   // FOR (i,0,n) cout << vals[i][0] << "," << vals[i][1] << "," << vals[i][2] << "," << vals[i][3] << '\n';
    pii tot = {0,0};
    FOR (i,0,n){
   //     cout << res[i].f << ',' << res[i].s << '\n';
        tot = comp(tot, res[i]);
    }
    cout << tot.f << " " << tot.s << '\n';
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 50520 KB Output is correct
2 Correct 8 ms 50520 KB Output is correct
3 Correct 8 ms 50616 KB Output is correct
4 Correct 9 ms 50612 KB Output is correct
5 Correct 10 ms 50780 KB Output is correct
6 Correct 12 ms 50780 KB Output is correct
7 Correct 12 ms 51036 KB Output is correct
8 Correct 14 ms 51036 KB Output is correct
9 Correct 24 ms 51800 KB Output is correct
10 Correct 31 ms 53084 KB Output is correct
11 Correct 43 ms 53584 KB Output is correct
12 Correct 89 ms 56892 KB Output is correct
13 Correct 102 ms 58196 KB Output is correct
14 Correct 121 ms 59468 KB Output is correct
15 Correct 134 ms 59952 KB Output is correct
16 Correct 140 ms 60756 KB Output is correct
17 Correct 164 ms 61264 KB Output is correct
18 Correct 114 ms 62036 KB Output is correct
19 Correct 157 ms 62700 KB Output is correct
20 Correct 171 ms 63384 KB Output is correct