Submission #80955

#	Time	Username	Problem	Language	Result	Execution time	Memory
80955		istlemin	Fish (IOI08_fish)	C++14	0 / 100	741 ms	66560 KiB

fish

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll m;

class Node{
    public:
        Node* left;
        Node* right;
        ll data = 1;
        ll up,dn;
        Node(ll DN, ll UP){
            dn = DN; up = UP;
            if(dn+1!=up){
                left = new Node(dn,(dn+up)/2);
                right = new Node((dn+up)/2,up);
            }
        }

        ll update(ll ind,ll val){
            if(ind<dn||ind>=up) return data;
            if(dn+1==up) return data = val;
            else return data = (left->update(ind,val)*right->update(ind,val)) % m;
        }
};

int main(){
	cin.sync_with_stdio(false);
	ll n,k;
	cin>>n>>k>>m;
    vector<pii> l(n);
    vector<vi> gems(k);
    rep(i,0,n) {
        cin>>l[i].first>>l[i].second;
        --l[i].second;
        gems[l[i].second].push_back(l[i].first);
    }
    rep(i,0,k) sort(all(gems[i]));
    sort(all(l));
    vector<bool> seen(k);
    vi numGems(k);
    Node st(0,k);
    rep(i,0,k) {
        numGems[i] = distance(gems[i].begin(),lower_bound(all(gems[i]),l[n-1].first/2+1));
        st.update(i,numGems[i]+1);
    }
    ll ans = 0;
    ll numFishes = distance(l.begin(),lower_bound(all(l),pii(l[n-1].first/2+1,0)));
    for(ll i = n-1;i>=0;--i){
        if(l[i].first*2<=l[n-1].first) break;
        while(numFishes>0&&l[numFishes-1].first>=l[i].first/2+1) {
            numGems[l[numFishes-1].second]--;
            st.update(l[numFishes-1].second,numGems[l[numFishes-1].second]+1);
            seen[l[numFishes-1].second] = true;
            numFishes--;
        }
        if(seen[l[i].second]) continue;
        seen[l[i].second] = true;
        st.update(l[i].second,1);
        ans = (ans+st.data)%m;
        st.update(l[i].second,numGems[l[i].second]+1);
    }
    cout<<ans-1<<endl;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5