oj.uz

Submission #920970

# Submission time Handle Problem Language Result Execution time Memory
920970 2024-02-03T08:31:10 Z simuyu Trampoline (info1cup20_trampoline) C++14
73 / 100
 2000 ms 23748 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define f first
#define s second

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


    // refer to paper.
    map<ll, set<pll> > m;
    ll r, c;
    long n, t;

    cin >> r >> c >> n;

    // offline processing - sort by x then y
    vector<pll > in;
    ll x, y;
    for (long i=0; i<n; i++) {
        cin >> x >> y;
        in.push_back(pll(x,y));
    }

    sort(in.begin(), in.end());

    // add to map
    ll prev = -3;
    ll cnt = 1;
    ll mag, start=in[0].f;
    vector<ll> earliests;

    for (long i=0; i<n; i++) {
        if (in[i].f-1 == prev && (earliests.size() == 0 || in[i].s >= earliests[earliests.size()-1] ) ){ // streak can be continued
            cnt++;
        } else if (in[i].f != prev) {
            // streak lost, move on to this new thing. do make the things in a binary way yes.
            // actually, find out how to implement streak later.

            /*
            mag = 2;
            while (mag <= cnt) {
                // make those that yes
                // from streak start, to current, inclusive and exclusive.
                for (ll s = start; s < in[i].f; s += cnt) {
                    // from s to s+cnt, by simulation

                }
            }
            */
            cnt = 1;
            start = in[i].f;
            earliests.clear();
        }
        // insert length 1 data to map
        if (!m.count(in[i].f)) { // initialize if needed
            m[in[i].f] = set<pll>();
        }
        m[in[i].f].insert(pll(in[i].s, 1));

        // add to earliest/latest
        if (in[i].f != prev) {
            earliests.push_back(in[i].s);
        }

        prev = in[i].f;
    }

    // note that streak thing hasn't been implemented yet, so it will be not optimal. but shld solve all subtasks except last, i think.

    cin >> t;
    ll fx, fy, tx, ty;
    for (long q=0; q<t; q++) {
        cin >> fx >> fy >> tx >> ty;
        if (fx > tx || fy > ty) {
            cout << "No" << '\n';
            continue;
        }

        while (fx != tx) {
            // since streak thing not yet implemented, just one by one
            if (!m.count(fx)) break; // means cannot.

            auto temp = m[fx].lower_bound(pll(fy,1));
            if (temp == m[fx].end()) break; // means cannot.
            fy = (*temp).f;
            fx += (*temp).s;
        }

        if (fx != tx) {
            cout << "No" << '\n';
            continue;
        }

        if (fy <= ty) {
            cout << "Yes" << '\n';
        } else {
            cout << "No" << '\n';
        }

    }


    //


    /*map<long, vector<long> > m;
    m[1] = vector<long>();
    cout << m.count(0) << ' ' << m.count(1) << endl;*/

    return 0;
}

Compilation message

trampoline.cpp: In function 'int main()':
trampoline.cpp:34:8: warning: unused variable 'mag' [-Wunused-variable]
   34 |     ll mag, start=in[0].f;
      |        ^~~
trampoline.cpp:34:13: warning: variable 'start' set but not used [-Wunused-but-set-variable]
   34 |     ll mag, start=in[0].f;
      |             ^~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 992 KB 200 token(s): yes count is 21, no count is 179
2 Correct 5 ms 1248 KB 200 token(s): yes count is 70, no count is 130
3 Correct 4 ms 860 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 16804 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 120 ms 16320 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 300 ms 16428 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 567 ms 16588 KB 4000 token(s): yes count is 1991, no count is 2009

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 16576 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 213 ms 16688 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 203 ms 16712 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 205 ms 17132 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 232 ms 17592 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 250 ms 23748 KB 200000 token(s): yes count is 97163, no count is 102837

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 860 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 9 ms 860 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 7 ms 1112 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 4 ms 860 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 313 ms 1000 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 4 ms 856 KB 5000 token(s): yes count is 3390, no count is 1610

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 23740 KB Time limit exceeded
2 Halted 0 ms 0 KB -