Submission #518590

#	Time	Username	Problem	Language	Result	Execution time	Memory
518590		blue	Sails (IOI07_sails)	C++17	100 / 100	328 ms	2536 KiB

sails

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int rt = 320;

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 << "\n\n";
            // cerr << "b = " << b << " : " << rt*b << " - " << rt*b + rt-1 << '\n';
            // cerr << tot[b] << " <> " << K << '\n';

            // cerr << "ins = " << ins << '\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';




                // cerr << "old block " << b << " : \n";
                // for(int w = 0; w < rt; w++) cerr << rt*b+w << " - " << freq[b][(st[b] + w) % rt] << '\n';

                // if(b == 0) cerr << "! " << rt*(b+1)+0 << " - " << freq[b+1][st[b+1]] << '\n';







                K -= tot[b];
                int new_ins = freq[b][ (st[b] + (rt-1)) % rt ];

                // cerr << "ni = " << new_ins << '\n';

                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';

                // cerr << "new block " << b << " : \n";
                // for(int w = 0; w < rt; w++) cerr << rt*b+w << " - " << freq[b][(st[b] + w) % rt] << '\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;
                tot[b] += ins;

                break;
            }
        }


        // cerr << "current config = \n";
        // 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';
        // cerr << "block sizes: \n";
        // for(int b = 0; b < rt; b++) cerr << b << " : " << tot[b] << '\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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10