oj.uz

답안 #1005204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1005204 2024-06-22T08:46:46 Z bachhoangxuan Fish (IOI08_fish) C++17
17 / 100
 314 ms 41040 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int maxn = 5e5+5;

int n,k,mod,mx[maxn];
vector<int> p[maxn];
int c[maxn],tree[4*maxn];

void build(int l,int r,int id){
    if(l==r){
        tree[id]=(c[l]+1)%mod;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,id<<1);build(mid+1,r,id<<1|1);
    tree[id]=tree[id<<1]*tree[id<<1|1]%mod;
}
void update(int l,int r,int id,int x){
    if(l==r){
        tree[id]=(c[l]+1)%mod;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) update(l,mid,id<<1,x);
    else update(mid+1,r,id<<1|1,x);
    tree[id]=tree[id<<1]*tree[id<<1|1]%mod;
}
int query(int l,int r,int id,int tl,int tr){
    if(tr<l || r<tl) return 1;
    if(tl<=l && r<=tr) return tree[id];
    int mid=(l+r)>>1;
    return query(l,mid,id<<1,tl,tr)*query(mid+1,r,id<<1|1,tl,tr)%mod;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> k >> mod;
    vector<pii> d;
    for(int i=1;i<=n;i++){
        int l,x;cin >> l >> x;
        mx[x]=max(mx[x],l);
        d.push_back({l,x});
    }
    vector<int> ord(k);
    iota(ord.begin(),ord.end(),1);
    sort(ord.begin(),ord.end(),[&](int x,int y){
        return mx[x]>mx[y];
    });
    for(int i=0;i<k;i++) mx[ord[i]]=i+1;
    for(auto &[l,x]:d) x=mx[x],p[x].push_back(l);
    for(int i=1;i<=k;i++){
        c[i]=(int)p[i].size();
        sort(p[i].begin(),p[i].end());
    }
    sort(d.begin(),d.end());
    build(1,k,1);

    int pos=1,total=0;
    for(int i=1;i<=k;i++){
        while(!d.empty() && d.back().fi>p[i].back()/2){
            int x=d.back().se;d.pop_back();
            c[x]--;update(1,k,1,x);
        }
        while(pos<=k && p[pos].back()/2>=p[i][c[i]]) pos++;
        int rt=(i==k?1:query(1,k,1,i+1,k));
        int lt=(pos<i?query(1,k,1,pos,i-1)-1:0);
        lt=(lt+c[i]+1)%mod;
        total=(total+lt*rt)%mod;
    }
    cout << total << '\n';
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16732 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 16728 KB Output is correct

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 16732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 16728 KB Output is correct

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Incorrect 3 ms 16732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Incorrect 127 ms 29652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 16732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 16988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 57 ms 22684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Incorrect 4 ms 16988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 87 ms 27080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 30904 KB Output is correct
2 Incorrect 141 ms 30876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 26316 KB Output is correct
2 Incorrect 150 ms 31332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 139 ms 32444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 165 ms 33460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 142 ms 30160 KB Output is correct
2 Correct 254 ms 35000 KB Output is correct

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 281 ms 38836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 257 ms 39528 KB Output is correct
2 Incorrect 257 ms 35196 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 314 ms 41040 KB Output isn't correct
2 Halted 0 ms 0 KB -