제출 #518579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
518579		blue	Sails (IOI07_sails)	C++17	25 / 100	347 ms	2628 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 << "b = " << b << '\n';
            if(tot[b] <= K)
            {
                // cerr << "case 1\n";
                st[b] = (st[b] - 1 + rt) % rt;

                int new_ins = freq[b][ st[b] + 0 ];

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

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

                ins = new_ins;

                K -= tot[b];
            }
            else
            {
                // cerr << "case 2\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(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(int o = 0; o < 10; o++) cerr << freq[0][st[0] + o] << ' ';
        // 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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10