oj.uz

Submission #518582

# Submission time Handle Problem Language Result Execution time Memory
518582 2022-01-24T07:40:45 Z blue Sails (IOI07_sails) C++17
0 / 100
 53 ms 65540 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int rt = 20'000;

using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    pii P[N];
    for(int i = 0; i < N; i++) cin >> P[i].first >> P[i].second;

    sort(P, P+N);


    vvi freq(rt, vi(rt, 0));
    vi tot(rt, 0);

    vi st(rt, 0);

    int mxh = 0;


    for(auto& p: P)
    {
        // cerr << "\n\n\n\n";
        int H = p.first;
        int K = p.second;
        // cerr << "sail = " << H << ' ' << K << '\n';

        while(mxh < H)
        {
            mxh++;
            // cerr << "inc height\n";
            freq[0][st[0] + 0]++;
            tot[0]++;
        }

        // cerr << "00 = " << freq[0][st[0]+0] << '\n';

        int ins = 0;

        for(int b = 0; b < rt; b++)
        {
            // cerr << "b = " << b << '\n';

            // cerr << freq[b][0] << ' ' << freq[b][1] << '\n';
            if(tot[b] <= K)
            {
                // cerr << "case 1\n";
                // cerr << b << " : " << tot[b] << '\n';
                // cerr << "K = " << K << '\n';
                K -= tot[b];
                int new_ins = freq[b][ (st[b] + (rt-1)) % rt ];

                st[b] = (st[b] - 1 + rt) % rt;

                tot[b] += ins - freq[b][ st[b] + 0 ];

                freq[b][ st[b] + 0 ] = ins;

                ins = new_ins;

                // K -= tot[b];

                // cerr << "new K = " << K << '\n';
            }
            else
            {
                // cerr << "case 2\n";
                // cerr << K << '\n';
                int z;
                int lstv;
                for(z = 0; z < rt; z++)
                {
                    lstv = min(K, freq[b][(st[b] + z) % rt]);
                    K -= lstv;
                    if(K <= 0) break;
                }

                // cerr << "z = " << z << '\n';
                // cerr << freq[b][st[b]+z] << '\n';
                // cerr << ins << ' ' << lstv << '\n';

                if(lstv > 0 && z == rt-1)
                {
                    // cerr << "next block\n";
                    freq[b+1][st[b+1] + 0] += lstv;
                    tot[b+1] += lstv;

                    freq[b][(st[b] + z) % rt] -= lstv;
                    tot[b] -= lstv;
                }
                else
                {
                    // cerr << "curr block\n";
                    // cerr << freq[b][(st[b] + z) % rt] << ' ' << freq[b][(st[b] + z + 1) % rt] << '\n';
                    freq[b][(st[b] + z + 1) % rt] += lstv;
                    freq[b][(st[b] + z) % rt] -= lstv;
                    // cerr << " -> ";
                    // cerr << freq[b][(st[b] + z) % rt] << ' ' << freq[b][(st[b] + z + 1) % rt] << '\n';
                }

                // for(int v = 0; v < 5; v++) cerr << freq[b][st[b]+v] << ' ';
                // cerr << '\n';

                for(int y = z-1; y >= 0; y--)
                {
                    // cerr << "y = " << y << '\n';
                    freq[b][(st[b] + y + 1) % rt] += freq[b][(st[b] + y) % rt];
                    freq[b][(st[b] + y) % rt] = 0;
                    // cerr << freq[b][(st[b] + y + 1) % rt] << '\n';
                }

                freq[b][st[b]] += ins;

                break;
            }
        }


        // for(ll sc = 0; sc < rt*rt; sc++)
        // {
        //     ll occ = freq[sc/rt][(st[sc/rt] + sc%rt) % rt];
        //
        //     // if(occ > 0) cerr << sc << " : " << occ << '\n';
        //
        //     // cerr << occ << ' ';
        // }
        // // cerr << '\n';
    }


    ll res = 0;
    for(ll sc = 0; sc < rt*rt; sc++)
    {
        ll occ = freq[sc/rt][(st[sc/rt] + sc%rt) % rt];

        // if(occ > 0) cerr << sc << " : " << occ << '\n';

        res += occ * ((sc-1) * sc) / 2;
    }

    cout << res << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -