Submission #920970

#	Time	Username	Problem	Language	Result	Execution time	Memory
920970		simuyu	Trampoline (info1cup20_trampoline)	C++14	73 / 100	2063 ms	23748 KiB

trampoline

#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 (stderr)

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 / 23
• Subtask 2: 20 / 20
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 0 / 27