oj.uz

Submission #80955

# Submission time Handle Problem Language Result Execution time Memory
80955 2018-10-23T09:07:12 Z istlemin Fish (IOI08_fish) C++14
0 / 100
 741 ms 66560 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 556 KB Output isn't correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 556 KB Output isn't correct

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 732 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 808 KB Output isn't correct

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 8932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 16044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 198 ms 27564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 172 ms 27564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 284 ms 37468 KB Output isn't correct

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 337 ms 47536 KB Output isn't correct

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 337 ms 54416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 677 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 362 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 741 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -