Submission #551409

#	Time	Username	Problem	Language	Result	Execution time	Memory
551409		BalintR	Ants and Sugar (JOI22_sugar)	C++17	6 / 100	4067 ms	3536 KiB

sugar

#include <bits/stdc++.h>
using namespace std;

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cmplx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound((v).begin(), (v).end(), x) - (v).begin())
#define ubv(v, x) (upper_bound((v).begin(), (v).end(), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cout << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cout << #arr; FR(_i, n) cout << ' ' << arr[_i]; cout << endl;}

int q, l;

int main(){
    boost();
    cin >> q >> l;

    vpii arr, brr;
    while(q--){
        int t, x, a;
        cin >> t >> x >> a;
        if(t == 1) arr.insert(lower_bound(ALL(arr), pii{x, -1}), pii{x, a});
        if(t == 2) brr.insert(lower_bound(ALL(brr), pii{x, -1}), pii{x, a});

        vpii acpy = arr, bcpy = brr;

        ll res = 0;
        int asz = SZ(arr), bsz = SZ(brr);
        int i = 0, j = 0;

        while(i < asz && j < bsz){
            if(abs(arr[i].fs - brr[j].fs) <= l){
                int mn = min(arr[i].sn, brr[j].sn);
                res += mn;
                arr[i].sn -= mn, brr[j].sn -= mn;
                if(!arr[i].sn) i++;
                if(!brr[j].sn) j++;
            }
            else if(arr[i].fs < brr[j].fs) i++;
            else j++;
        }

        arr = acpy, brr = bcpy;
        cout << res << '\n';
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 26
• Subtask 4: 0 / 52