oj.uz

Submission #518579

# Submission time Handle Problem Language Result Execution time Memory
518579 2022-01-24T07:15:32 Z blue Sails (IOI07_sails) C++17
25 / 100
 347 ms 2628 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 692 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 696 KB Output is correct
2 Correct 1 ms 692 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 688 KB Output is correct
2 Correct 1 ms 700 KB Output is correct

Subtask #4
0 / 5.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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