Submission #494435

#	Time	Username	Problem	Language	Result	Execution time	Memory
494435		danikoynov	Food Court (JOI21_foodcourt)	C++14	7 / 100	385 ms	524292 KiB

foodcourt

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;
const ll maxn = 250010;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

struct Treap
{
    struct Node
    {
        ll pr, key, sz, key_sum, gr;
        Node *l, *r;

        Node(ll _key, ll _gr)
        {
            gr = _gr;
            sz = 1;
            pr = rand();
            key = _key;
            key_sum = _key;
            l = r = NULL;
        }

        void prll()
        {
            if (l) l -> prll();
            cout << key << " ";
            if (r) r -> prll();
        }
        void con()
        {
            sz = 1;
            key_sum = key;
            if (l)
            {
                sz += l -> sz;
                key_sum += l -> key_sum;
            }
            if (r)
            {
                sz += r -> sz;
                key_sum += r -> key_sum;
            }
        }
    };

    Node *root = NULL;

    void SplitSum(Node *T, Node *&L, Node *&R, ll qsum)
    {
        if (T == NULL)
        {
            L = R = NULL;
            return;
        }

        ll sum = T -> key;
        if (T -> l)
            sum += T -> l -> key_sum;

        if (qsum >= sum)
        {
            L = T;
            SplitSum(T -> r, L -> r, R, qsum - sum);
        }
        else
        {
            R = T;
            SplitSum(T -> l, L, R -> l, qsum);
        }

        T -> con();
    }

    void SplitSize(Node *T, Node *&L, Node *&R, ll qsize)
    {
        ///cout << "again" << endl;
        if (T == NULL)
        {
            L = R = NULL;
            return;
        }

        ll _sz = 1;
        if (T -> l)
            _sz += T -> l -> sz;

        ///cout << T -> key << " " << _sz << endl;

        if (qsize >= _sz)
        {
            L = T;
            SplitSize(T -> r, L -> r, R, qsize - _sz);
        }
        else
        {
            ///cout << "hey" << endl;
            R = T;
            SplitSize(T -> l, L, R -> l, qsize);
        }

        T -> con();
    }

    void Merge(Node *&T, Node *L, Node *R)
    {
        if (L == NULL && R == NULL)
        {
            T = NULL;
            return;
        }

        if (L == NULL)
        {
            T = R;
            return;
        }

        if (R == NULL)
        {
            T = L;
            return;
        }

        if (L -> pr > R -> pr)
        {
            T = L;
            Merge(T -> r, L -> r, R);
        }
        else
        {
            T = R;
            Merge(T -> l, L, R -> l);
        }

        T -> con();
    }

    void Insert(ll _key, ll _gr)
    {
        ///cout << "Insert" << endl;
        Node *M = new Node(_key, _gr);
        Merge(root, root, M);
    }

    void Erase(ll k)
    {
        if (root == NULL)
            return;
        if (root -> key_sum <= k)
        {
            root = NULL;
            return;
        }


        Node *L, *M, *R;
        SplitSum(root, L, R, k);

        if (L != NULL)
            k -= L -> key_sum;

        if (k != 0)
        {
            SplitSize(R, M, R, 1);
            M -> key -= k;
            M -> key_sum -= k;
            Merge(R, M, R);
        }
        root = R;
    }


    ll query(ll pos)
    {
        if (root == NULL)
            return 0;
        if (root -> key_sum < pos)
            return 0;
        ///cout << root -> key_sum << endl;
        Node *L, *M, *R;
        SplitSum(root, L, R, pos - 1);
        SplitSize(R, M, R, 1);
        ll ans = M -> gr;
        Merge(R, M, R);
        Merge(root, L, R);
        return ans;
    }
};

ll n, m, q;
Treap tree[4 * maxn];
struct lazy_query
{
    ll k, c, tim;
};
vector < lazy_query >lazy_add[4 * maxn], lazy_rem[4 * maxn];

void push_lazy(ll root, ll left, ll right)
{
    if (left != right)
    {
        for (ll j = 0; j < lazy_add[root].size(); j ++)
        {
            lazy_add[root * 2].push_back(lazy_add[root][j]);
            lazy_add[root * 2 + 1].push_back(lazy_add[root][j]);
        }
        for (ll j = 0; j < lazy_rem[root].size(); j ++)
        {
            lazy_rem[root * 2].push_back(lazy_rem[root][j]);
            lazy_rem[root * 2 + 1].push_back(lazy_rem[root][j]);
        }
    }
    if (left == right)
    {
        ll j1 = 0;
        ll j2 = 0;
        while(j1 < lazy_add[root].size() && j2 < lazy_rem[root].size())
        {
            if (lazy_add[root][j1].tim < lazy_rem[root][j2].tim)
            {
                tree[root].Insert(lazy_add[root][j1].k, lazy_add[root][j1].c);
                j1 ++;
            }
            else
            {
                tree[root].Erase(lazy_rem[root][j2].k);
                j2 ++;
            }
        }

        while(j1 < lazy_add[root].size())
        {
            tree[root].Insert(lazy_add[root][j1].k, lazy_add[root][j1].c);
            j1 ++;
        }

        while(j2 < lazy_rem[root].size())
        {
            tree[root].Erase(lazy_rem[root][j2].k);
            j2 ++;
        }
    }
    lazy_add[root].clear();
    lazy_rem[root].clear();
    ///if (tree[root].root != NULL)
    /// cout << left << " - " << right << " " << tree[root].root -> key_sum << endl;
}

void update_range(ll root, ll left, ll right,
                  ll qleft, ll qright, ll c, ll k, ll t, ll idx)
{

    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;
///cout << root << " - " << left << " " << right << " " << qleft << " " << qright << " " <<c << " " << k << endl;
    if (left >= qleft && right <= qright)
    {
        ///cout << "here" << endl;
        if (t == 1)
            lazy_add[root].push_back({k, c, idx});
        else
            lazy_rem[root].push_back({k, c, idx});
        push_lazy(root, left, right);
        return;
    }

    ll mid = (left + right) / 2;
    update_range(root * 2, left, mid, qleft, qright, c, k, t, idx);
    update_range(root * 2 + 1, mid + 1, right, qleft, qright, c, k, t, idx);

}

ll point_query(ll root, ll left, ll right, ll idx, ll k)
{
    push_lazy(root, left, right);
    if (left == right)
        return tree[root].query(k);

    ll mid = (left + right) / 2;
    if (idx <= mid)
    {
        return point_query(root * 2, left, mid, idx, k);
    }
    else
    {
        return point_query(root * 2 + 1, mid + 1, right, idx, k);
    }
}
void solve()
{
    cin >> n >> m >> q;
    for (ll i = 1; i <= q; i ++)
    {
        ll type;
        cin >> type;
        if (type == 1)
        {
            ll l, r, c, k;
            cin >> l >> r >> c >> k;
            update_range(1, 1, n, l, r, c, k, 1, i);
        }
        else if (type == 2)
        {
            ll l, r, k;
            cin >> l >> r >> k;
            update_range(1, 1, n, l, r, 0, k, 2, i);
        }
        else
        {
            ll a, b;
            cin >> a >> b;
            ll ans = point_query(1, 1, n, a, b);
            cout << ans << endl;
        }
    }
}
int main()
{
    speed();
    solve();
    return 0;
}
/**
1457 236823 1554
1 282 1270 166817 1
2 258 413 1
3 71 1
1 599 1196 220672 1
1 603 1271 178260 1
3 976 3
3 256 3
1 1182 1212 136739 1
3 516 1
2 248 1296 1
1 294 1116 168521 1
2 1215 1237 1
1 113 930 135524 1
3 1163 1
2 99 1373 1
2 10 1191 1
1 572 1409 218332 1
3 944 2
2 253 1397 1
2 145 961 1
2 742 1331 1
2 299 370 1
1 165 216 181315 1
3 1299 2
1 235 852 48483 1
2 318 1066 1
3 316 1
2 316 616 1
2 112 253 1
2 112 964 1
2 396 726 1
3 1163 2
2 1071 1275 1
1 92 548 136574 1
1 501 948 56393 1
3 1068 3
2 253 1112 1
1 872 1007 206029 1
3 978 1
3 710 1
1 254 493 179488 1
3 947 1
1 312 799 9301 1
1 549 696 10905 1
2 149 1390 1
2 729 1173 1
1 694 1279 217617 1
2 76 1133 1
1 116 1232 146603 1
1 13 810 100282 1
1 6 344 215222 1
1 489 1136 133025 1
2 418 923 1
2 1314 1447 1
2 712 1116 1
2 710 1247 1
1 87 464 114271 1
3 600 2
2 132 1124 1
1 72 380 197559 1
3 1045 2
3 691 1
3 18 24
2 119 1156 1
3 367 1
2 123 471 1
3 608 3
3 1430 2
3 355 6
2 158 737 1
1 79 1001 128535 1
2 151 200 1
2 1188 1303 1
3 499 1
1 215 1191 101217 1
3 1341 3
1 251 1063 3126 1
2 196 456 1
3 654 3
2 410 784 1
1 315 467 152881 1
3 1040 2
2 690 1225 1
1 1138 1285 186572 1
1 318 325 81729 1
2 563 835 1
2 717 1072 1
3 1407 2
2 722 1253 1
1 247 1454 122524 1
3 481 2
2 201 468 1
1 269 341 141826 1
1 172 220 198675 1
1 710 918 96134 1
3 842 1
3 138 12
2 36 1036 1
2 521 580 1
3 1232 2
2 67 667 1
2 733 1211 1
2 131 1068 1
3 53 1
3 286 1
3 735 2
3 975 1
2 248 700 1
3 1179 2
2 1075 1239 1
2 327 504 1
1 137 968 152680 1
2 865 1310 1
3 71 1
1 1161 1403 154127 1
2 628 653 1
3 1268 35
1 149 819 65671 1
1 235 1327 179151 1
1 6 1242 58728 1
2 275 1447 1
1 579 644 10839 1
1 348 359 106959 1
3 184 2
2 360 625 1
3 1283 4
1 371 1166 225339 1
3 265 4
3 315 5
1 139 1178 186093 1
1 971 1172 34272 1
2 129 703 1
1 538 1089 18973 1
1 57 463 137633 1
2 1211 1372 1
3 329 3
1 855 1206 204736 1
3 388 1
3 1070 2
2 352 880 1
3 769 7
3 768 6
2 900 901 1
1 1125 1264 12440 1
2 795 1030 1
3 1091 4
1 283 343 108816 1
2 141 1364 1
2 423 458 1
3 1421 33
2 337 460 1
3 329 12
1 479 954 6242 1
1 122 124 90749 1
1 667 942 47634 1
2 640 821 1
2 334 790 1
1 693 782 119408 1
1 403 1298 135340 1
3 827 4
2 707 1347 1
3 973 3
3 325 2
3 852 4
3 1229 2
2 835 999 1
1 863 928 121804 1
2 50 1200 1
2 327 376 1
3 82 3
1 91 615 51190 1
1 924 1414 49876 1
3 731 2
1 3 496 182111 1
2 54 905 1
3 478 1
3 468 1
3 580 10
1 308 749 127794 1
3 1334 3
2 7 1412 1
2 169 1098 1
3 308 22
1 899 1367 126929 1
3 202 3
2 629 867 1
2 107 1171 1
2 406 559 1
1 324 537 42572 1
1 140 1326 5355 1
2 589 688 1
2 916 1314 1
2 889 1379 1
2 323 855 1
1 1158 1281 222019 1
2 31 963 1
1 32 493 219627 1
1 36 813 134095 1
2 411 659 1
3 1169 10
1 596 1152 132372 1
1 276 625 110156 1
3 84 4
3 1021 2
1 346 1234 191745 1
2 168 585 1
3 768 3
2 167 1302 1
1 32 633 104231 1
3 195 1
2 954 1299 1
1 168 1088 108117 1
2 70 464 1
2 705 1257 1
1 70 1295 16272 1
3 342 2
2 76 182 1
3 92 4
2 194 1214 1
2 845 1403 1
2 821 937 1
1 41 914 158731 1
1 657 936 149410 1
1 556 577 205945 1
1 383 565 22591 1
3 112 5
1 712 1147 114032 1
1 718 886 57036 1
3 332 4
2 257 462 1
3 9 1
1 636 1176 25452 1
3 1036 1
1 82 499 16960 1
1 1181 1397 184857 1
3 172 2
1 24 1034 111074 1
1 779 1316 218722 1
2 980 1178 1
1 172 976 151099 1
2 223 353 1
1 526 1037 26302 1
1 756 906 132691 1
1 109 290 29773 1
2 6 846 1
2 413 1365 1
3 1237 1
2 851 1439 1
3 1077 1
1 169 878 152489 1
1 1 898 122104 1
1 431 973 53578 1
1 264 768 42961 1
1 509 1102 124583 1
2 699 1451 1
1 713 916 206947 1
1 1128 1293 13563 1
2 879 1282 1
3 242 22
2 142 356 1
2 207 1443 1
3 1319 1
1 68 746 45689 1
2 824 918 1
1 667 877 214720 1
2 120 297 1
1 1175 1417 118671 1
1 525 577 226409 1
2 142 181 1
2 213 1224 1
1 201 1216 118009 1
2 806 1335 1
3 59 3
3 815 19
3 534 7
2 457 1128 1
1 89 615 90790 1
1 1133 1153 147507 1
3 628 28
3 135 6
2 457 511 1
3 1075 1
3 545 27
2 1078 1184 1
3 664 10
2 462 1403 1
1 170 584 220060 1
1 198 370 122818 1
1 299 632 126295 1
2 361 1122 1
3 907 2
3 928 2
3 1417 1
1 42 685 140643 1
3 1305 1
2 1278 1394 1
1 402 677 101144 1
2 318 800 1
3 188 11
3 1084 3
2 31 660 1
2 723 1122 1
2 108 1153 1
3 554 11
1 922 1445 99721 1
1 505 1417 127946 1
3 387 3
1 360 677 59268 1
1 399 1096 48866 1
1 290 1189 72596 1
3 590 12
3 463 2
1 757 1118 125103 1
3 452 35
2 202 280 1
1 294 969 162779 1
1 1157 1410 235371 1
2 354 533 1
1 76 552 138799 1
1 745 783 46920 1
3 104 5
1 1065 1154 122412 1
2 820 1102 1
3 542 15
3 794 32
2 559 684 1
3 1397 3
3 201 2
2 421 1289 1
2 178 754 1
1 1210 1301 139483 1
2 393 724 1
2 15 459 1
2 406 1194 1
3 393 9
1 1015 1254 137509 1
1 694 1206 94035 1
3 418 7
1 1053 1376 223346 1
3 81 5
3 1385 2
1 460 697 221138 1
2 568 977 1
2 722 745 1
2 19 1200 1
2 70 618 1
2 1010 1145 1
1 612 1167 121648 1
1 1232 1452 51928 1
1 83 553 161593 1
1 278 818 61716 1
2 749 845 1
1 321 787 185654 1
1 229 834 67764 1
2 273 632 1
2 293 390 1
1 692 1243 190440 1
1 58 961 157697 1
3 1322 5
3 25 2
3 1224 3
1 480 1006 136992 1
3 1385 1
1 837 1186 128761 1
2 988 1346 1
2 67 1145 1
3 1343 5
1 349 1079 25418 1
3 1170 4
1 971 1170 124654 1
2 742 1127 1
2 526 1415 1
1 375 736 123915 1
2 276 694 1
2 939 1288 1
3 35 1
3 1397 93
3 423 8
2 471 1442 1
1 228 384 208107 1
3 1095 4
3 84 6
3 267 4
2 367 1193 1
2 315 568 1
3 917 1
2 300 648 1
3 901 121
3 970 2
1 392 503 224016 1
1 782 1262 41527 1
3 293 8
2 448 823 1
2 312 1220 1
1 64 182 90639 1
2 338 909 1
2 251 1028 1
3 1374 3
1 540 1125 76879 1
3 213 4
1 264 645 162367 1
1 528 567 113250 1
2 887 1244 1
2 800 828 1
2 293 1064 1
1 686 1356 218924 1
3 384 6
3 172 5
1 105 1215 78600 1
1 1171 1427 212374 1
2 341 1371 1
1 711 1061 106816 1
3 569 9
1 48 260 187994 1
2 959 1350 1
2 169 323 1
2 1044 1361 1
3 174 2
2 495 639 1
1 36 323 134435 1
3 1175 1
1 76 1041 126066 1
3 1220 2
3 767 7
3 661 23
3 229 4
2 1030 1230 1
3 67 1
3 532 16
2 949 1028 1
1 166 1049 89549 1
2 699 1069 1
3 1188 3
3 51 5
1 1020 1315 219186 1
2 413 437 1
3 693 10
3 158 11
1 783 861 72635 1
1 312 983 128436 1
2 76 658 1
2 84 327 1
1 211 795 43620 1
1 149 967 137381 1
3 1256 4
2 424 1404 1
2 288 409 1
3 267 8
1 537 1191 234795 1
2 125 232 1
2 264 691 1
3 57 18
2 102 637 1
3 1309 2
1 78 870 124087 1
1 401 423 64994 1
3 1252 2
3 54 7
1 563 1070 20641 1
3 922 19
2 684 1332 1
2 900 1448 1
2 812 1317 1
2 714 1223 1
2 447 1029 1
3 627 3
3 1264 3
1 153 845 234519 1
2 340 1187 1
2 1066 1385 1
3 914 1
1 786 1446 81911 1
3 904 3
2 4 1325 1
3 751 22
2 232 981 1
2 580 729 1
3 1220 138
3 270 7
2 1084 1341 1
2 650 1412 1
3 1172 2
1 644 758 3704 1
1 1008 1398 76219 1
3 790 12
1 726 1099 95079 1
3 274 162
1 338 1385 216167 1
2 981 1055 1
3 458 5
2 247 654 1
3 1240 2
1 235 1379 94785 1
1 519 983 124862 1
3 414 9
1 552 792 213356 1
3 689 11
1 950 1259 149633 1
2 370 752 1
3 609 7
2 225 1326 1
1 307 1007 198863 1
3 591 6
1 362 801 158012 1
3 753 16
1 113 649 183078 1
1 981 1263 74433 1
1 553 601 224142 1
1 575 623 596 1
3 1058 84
3 368 15
2 120 685 1
3 556 2
3 1280 1
2 137 327 1
2 512 940 1
3 1441 1
3 591 1
2 261 792 1
2 655 1076 1
2 304 1135 1
2 450 973 1
2 404 1403 1
1 751 1196 61477 1
3 1036 1
3 1377 2
1 1416 1424 64128 1
1 724 998 126297 1
2 700 932 1
3 1339 2
2 287 837 1
3 620 2
2 151 418 1
1 436 807 231659 1
1 622 1187 226669 1
1 648 692 141704 1
1 1076 1389 235042 1
1 847 1341 68863 1
2 204 932 1
3 1000 6
2 78 224 1
1 367 651 157467 1
3 237 8
2 312 1090 1
2 3 878 1
2 458 612 1
3 742 16
1 1078 1243 51650 1
2 231 706 1
1 170 1047 130055 1
3 630 2
3 177 14
1 187 1044 230310 1
1 298 1446 162828 1
1 554 1097 223340 1
2 250 564 1
3 470 1
3 1441 2
3 1324 9
2 491 592 1
2 967 1456 1
3 1370 3
2 258 512 1
1 237 1249 37160 1
1 338 1449 204923 1
1 547 704 217411 1
1 311 1250 98567 1
1 374 1249 189641 1
1 287 1335 164160 1
3 640 26
1 157 499 217368 1
2 1014 1076 1
2 516 666 1
3 304 8
3 122 8
2 107 1229 1
3 1060 16
2 168 921 1
3 601 6
3 908 8
3 379 4
2 550 1097 1
3 119 16
3 1399 2
1 213 410 186308 1
1 751 884 233529 1
1 101 1019 140644 1
3 16 2
1 354 1363 223602 1
2 183 550 1
3 246 1
1 129 872 121384 1
3 147 1
1 682 802 95590 1
2 188 1314 1
2 781 1286 1
2 141 698 1
3 306 1
3 1304 7
3 331 1
2 1188 1283 1
2 712 997 1
3 11 1
3 756 8
2 480 1333 1
1 601 1223 179339 1
2 37 602 1
1 180 692 50446 1
3 1429 2
2 55 382 1
1 229 1081 152952 1
3 807 5
1 675 1078 179623 1
2 1167 1388 1
1 191 1021 176664 1
1 1045 1320 178471 1
3 1140 12
2 431 728 1
2 362 500 1
1 709 1030 124520 1
1 665 1014 76488 1
2 5 222 1
2 939 1191 1
2 198 1379 1
2 271 1180 1
2 457 882 1
1 504 1057 233508 1
2 128 1135 1
1 352 983 793 1
2 772 1221 1
1 135 1159 116507 1
3 72 5
2 938 1160 1
2 4 90 1
3 1145 4
3 58 2
1 392 582 103799 1
2 134 1153 1
3 1141 20
2 1056 1340 1
3 531 2
2 442 1302 1
1 282 1190 116731 1
3 424 8
2 30 596 1
2 488 807 1
2 914 1186 1
1 119 546 120466 1
1 848 1170 11130 1
1 131 1084 120347 1
3 697 12
2 690 1304 1
3 474 4
2 164 1009 1
3 978 4
3 51 3
2 279 1374 1
2 1077 1097 1
1 100 678 118392 1
1 1245 1446 124532 1
3 665 35
1 346 851 218647 1
2 401 1424 1
1 622 647 114601 1
1 946 1434 162701 1
1 673 1393 168554 1
1 57 1324 186376 1
3 902 24
2 864 1406 1
2 900 1069 1
2 153 1040 1
1 203 961 70781 1
1 117 1423 153 1
3 452 5
2 408 949 1
2 238 867 1
3 470 171
3 212 14
2 129 1285 1
3 557 5
1 1056 1311 25669 1
1 680 1448 60131 1
3 592 2
1 148 1234 110745 1
1 88 443 21333 1
3 1177 8
1 245 962 196257 1
2 136 773 1
1 1141 1383 41224 1
1 513 1435 115022 1
1 204 1080 181785 1
3 59 3
3 798 2
2 181 1380 1
3 1396 4
2 835 1112 1
2 135 1349 1
2 220 1043 1
3 469 1
1 743 750 119369 1
2 350 1399 1
2 204 1090 1
2 1381 1387 1
3 1024 1
1 351 440 93957 1
1 200 691 2467 1
3 1161 8
1 180 329 40776 1
2 539 794 1
3 1216 3
1 734 1053 42886 1
1 24 213 73998 1
2 324 1341 1
3 900 7
1 337 1108 100731 1
3 346 1
3 1188 5
2 215 1399 1
3 846 5
2 535 760 1
2 155 1443 1
2 580 1244 1
1 1034 1218 189984 1
1 52 1201 68359 1
1 567 653 40705 1
2 12 1369 1
1 26 1358 89266 1
2 223 258 1
3 780 13
1 719 1082 200446 1
2 956 1413 1
3 537 1
1 82 428 192011 1
2 680 805 1
1 188 946 170219 1
3 756 161
1 888 1034 220096 1
2 612 786 1
1 437 810 168340 1
1 891 1274 31705 1
3 915 1
1 496 1173 122607 1
1 173 1200 135535 1
1 878 1111 46681 1
1 245 1425 70655 1
1 656 1395 128627 1
3 1052 8
3 278 6
3 110 3
1 771 1075 4579 1
1 793 882 150199 1
2 771 1120 1
3 1369 197
1 129 1432 226810 1
3 1151 3
3 1264 4
3 761 125
1 479 1429 116020 1
2 453 914 1
1 62 542 46782 1
2 110 972 1
3 826 14
1 546 1406 161128 1
3 601 8
3 448 7
1 182 1327 74972 1
2 142 911 1
3 969 26
1 263 310 124008 1
3 147 6
1 547 1281 182047 1
3 142 5
3 798 22
2 1260 1448 1
2 1320 1446 1
2 349 838 1
2 719 739 1
2 1101 1311 1
3 1232 9
2 982 1092 1
2 108 1105 1
2 731 1408 1
2 890 1018 1
3 1312 4
1 464 658 19718 1
3 955 8
1 77 1392 13457 1
2 495 1060 1
1 117 1341 190210 1
1 1120 1159 195975 1
2 33 1183 1
3 179 2
2 638 907 1
2 626 1042 1
1 666 949 191696 1
1 730 929 117932 1
1 615 1326 221915 1
1 366 685 44304 1
2 178 1025 1
1 411 593 2247 1
3 833 11
1 339 428 132217 1
2 1218 1291 1
3 600 8
1 385 535 215175 1
2 322 624 1
1 324 788 100019 1
2 140 348 1
3 1387 3
3 40 32
3 669 12
3 125 10
1 314 597 33866 1
2 10 1195 1
1 14 1408 6773 1
1 111 886 193898 1
2 92 1399 1
1 286 947 93422 1
1 550 1058 179801 1
3 772 1
3 1065 13
3 736 16
3 439 63
3 255 1
3 441 3
2 661 1245 1
2 909 909 1
2 278 622 1
1 542 1175 179450 1
1 312 1330 229571 1
1 220 953 84640 1
3 1406 13
3 741 30
1 747 950 7239 1
3 577 32
2 245 1008 1
1 829 1382 13312 1
3 67 1
3 1361 6
2 118 562 1
1 1224 1422 46597 1
3 29 1
3 276 4
3 638 34
3 487 2
1 98 261 135702 1
3 532 5
3 266 163
2 891 896 1
1 1170 1329 185267 1
2 392 1303 1
1 489 822 104302 1
1 311 941 103572 1
3 852 8
3 425 3
1 922 966 102861 1
3 617 1
3 1085 12
3 65 10
3 277 6
3 125 7
2 513 770 1
3 1347 12
1 267 1067 185557 1
1 433 883 216609 1
2 263 1074 1
1 773 1427 36635 1
3 1212 14
2 247 328 1
2 630 1179 1
3 584 13
3 1356 9
3 1200 10
1 183 1292 127537 1
2 389 1221 1
3 1300 9
2 879 1359 1
1 856 1007 4295 1
1 75 354 211444 1
3 1095 15
3 40 1
3 1005 10
3 977 3
3 1068 12
2 221 521 1
1 1132 1316 63947 1
3 384 13
3 464 7
2 508 1071 1
3 540 4
1 991 1009 20908 1
3 1358 3
2 386 692 1
2 893 1091 1
1 1123 1260 10289 1
3 1146 15
1 547 833 168343 1
3 341 4
3 626 12
2 1131 1412 1
2 268 1122 1
1 350 968 127385 1
2 595 1323 1
3 773 24
1 143 690 18151 1
2 258 1008 1
3 328 1
3 470 5
2 527 1419 1
1 277 1448 21309 1
2 459 526 1
3 1269 10
2 647 1071 1
1 651 1187 213918 1
1 165 523 195485 1
1 39 450 140727 1
2 691 1342 1
2 659 1420 1
2 60 1222 1
1 755 1350 84210 1
1 631 957 97685 1
3 1187 13
3 187 11
1 538 1448 125537 1
1 903 1353 228586 1
2 40 704 1
2 988 1211 1
2 813 1376 1
1 605 1030 118087 1
3 644 29
3 592 14
1 277 714 140688 1
3 357 7
2 1101 1177 1
2 138 1336 1
2 350 547 1
2 771 1249 1
1 920 935 67660 1
1 226 1445 230671 1
1 597 684 86841 1
2 210 456 1
3 1158 14
1 530 1318 23979 1
1 806 951 145596 1
2 1036 1123 1
1 429 1056 77512 1
1 1042 1194 91911 1
3 485 8
2 953 1016 1
1 813 822 5885 1
2 113 503 1
1 128 1375 156833 1
1 42 1187 129095 1
3 28 2
3 1451 2
1 680 1052 58039 1
1 532 647 139846 1
1 888 1325 191148 1
2 226 1354 1
3 22 1
2 358 921 1
1 94 1308 40802 1
2 969 1098 1
3 1279 12
2 776 1111 1
1 1116 1455 105476 1
1 339 938 38757 1
2 484 758 1
2 957 1062 1
3 742 21
3 814 41
2 719 1357 1
3 985 6
3 13 1
2 477 1065 1
1 796 1273 85825 1
2 1019 1054 1
2 130 594 1
2 595 731 1
3 1040 1
2 1047 1387 1
3 274 2
1 589 1180 98692 1
1 641 730 82997 1
2 821 940 1
2 374 592 1
1 725 909 129853 1
1 843 1010 229523 1
1 359 795 20700 1
1 128 705 139435 1
1 801 980 226987 1
1 203 237 117621 1
1 764 1003 211289 1
1 645 927 121144 1
3 518 5
3 1141 19
2 347 448 1
1 411 1057 171690 1
2 376 399 1
2 42 627 1
2 913 1449 1
1 311 1442 164305 1
3 226 6
2 674 760 1
2 1089 1259 1
3 1211 10
1 624 1454 203152 1
1 999 1056 145229 1
2 871 1033 1
2 376 511 1
1 643 1099 216940 1
3 299 4
1 254 1372 134785 1
2 694 771 1
3 556 273
3 732 25
3 1376 10
1 120 886 235255 1
3 1253 17
1 736 914 139388 1
3 1446 5
3 330 4
1 278 1011 139643 1
2 303 545 1
2 1309 1407 1
2 29 793 1
2 343 557 1
3 367 13
1 778 1368 93238 1
1 82 173 207992 1
2 1236 1237 1
3 336 11
3 257 13
3 319 10
1 219 780 1682 1
1 1015 1392 15126 1
2 223 550 1
3 709 7
3 102 14
3 604 9
2 553 1166 1
1 69 735 168751 1
1 848 1218 156854 1
2 125 492 1
1 638 1440 99674 1
3 254 3
3 769 28
2 373 1280 1
3 505 29
2 1418 1449 1
2 469 946 1
2 741 1112 1
1 249 1369 212067 1
3 124 1
3 589 4
1 201 797 129187 1
2 1006 1158 1
3 340 13
1 339 545 204433 1
1 487 1087 41702 1
3 1239 10
3 480 4
1 340 1127 212072 1
2 7 531 1
2 87 364 1
1 71 485 85345 1
2 871 1214 1
3 574 3
2 1244 1390 1
2 751 1329 1
3 592 9
3 203 11
1 1123 1192 233113 1
1 914 1016 91977 1
3 908 30
3 528 11
2 1035 1132 1
2 1148 1209 1
3 710 21
3 1160 18
2 789 1149 1
1 210 816 51092 1
3 576 10
3 911 29
1 827 994 175140 1
1 407 454 61261 1
3 517 6
1 56 1110 144229 1
2 658 1259 1
3 205 154
3 760 21
2 179 216 1
3 1143 17
3 596 1
3 4 2
1 60 316 49757 1
2 468 1107 1
3 182 15
3 384 7
3 233 6
3 420 18
1 1301 1455 33448 1
1 797 943 66227 1
3 264 10
1 846 1342 23957 1
1 339 1055 234359 1
2 665 1098 1
1 147 221 32495 1
3 464 13
3 697 281
2 916 1149 1
2 1093 1436 1
1 136 619 198144 1
2 531 1302 1
2 149 864 1
3 1020 4
2 91 1277 1
2 198 1075 1
1 571 735 187314 1
2 42 721 1
1 544 1114 193198 1
3 322 8
2 846 1398 1
3 655 27
2 943 1222 1
3 248 6
1 273 704 222423 1
2 120 430 1
1 331 842 79928 1
3 31 2
1 754 871 49585 1
3 851 36
3 657 120
1 640 1293 188366 1
3 1129 5
3 1115 122
3 760 26
2 835 1223 1
2 566 940 1
2 1456 1456 1
2 195 1403 1
2 624 631 1
1 124 1287 36209 1
2 658 781 1
1 1246 1287 7262 1
1 514 1164 29544 1
3 395 14
1 148 577 23047 1
2 24 741 1
3 1116 4
1 972 1056 227118 1
1 577 1252 46480 1
1 541 1060 163512 1
3 487 4
3 1420 5
3 1398 4
3 586 74
3 129 28
2 300 378 1
1 990 1359 78549 1
2 671 965 1
3 825 19
1 587 1189 35997 1
2 194 897 1
2 224 1327 1
1 201 718 221409 1
2 229 581 1
1 1382 1434 226240 1
2 123 942 1
1 24 1071 159459 1
1 769 1271 141660 1
1 542 1376 125013 1
3 60 1
1 815 1113 119583 1
3 385 16
1 119 322 196251 1
3 636 9
2 266 1007 1
3 1070 1
2 278 1130 1
3 1356 8
2 422 1092 1
2 862 1008 1
1 69 272 220864 1
3 1033 11
2 435 920 1
3 627 23
1 159 321 99049 1
2 572 1006 1
2 1301 1323 1
2 84 683 1
1 1011 1058 225422 1
3 693 5
2 669 1242 1
3 1128 7
1 524 884 137485 1
2 394 1326 1
3 466 3
2 433 1006 1
1 273 718 114599 1
3 150 7
1 822 1149 203937 1
1 371 431 84069 1
1 736 1353 106491 1
1 523 1169 37511 1
2 345 1357 1
2 937 1009 1
1 174 379 87471 1
1 640 1210 219105 1
2 290 436 1
2 268 400 1
3 21 2
3 878 295
3 1376 9
1 217 1239 81486 1
3 654 58
2 137 824 1
1 936 1186 166280 1
1 122 1297 161044 1
1 442 951 199762 1
2 506 993 1
1 505 994 25558 1
1 307 360 157457 1
3 453 5
2 919 1188 1
2 373 1183 1
2 661 832 1
2 548 625 1
2 883 1189 1
2 462 793 1
2 459 620 1
2 614 897 1
2 242 347 1
1 1265 1409 193230 1
1 563 1259 226120 1
1 58 199 224454 1
2 20 1010 1
1 124 1388 77229 1
1 247 1015 75104 1
2 800 939 1
1 48 1185 195775 1
1 812 976 190819 1
1 968 1088 179210 1
1 1187 1198 161310 1
1 871 882 93884 1
3 756 7
3 453 4
1 179 898 15118 1
3 1083 10
3 692 19
3 298 3
2 14 204 1
1 214 220 54494 1
3 1336 13
1 17 265 53959 1
2 1318 1350 1
1 227 1265 40444 1
1 398 828 207557 1
3 737 375
1 146 699 24168 1
2 776 1405 1
1 358 530 127256 1
2 166 942 1
1 522 1007 181991 1
1 112 809 220563 1
3 565 14
2 602 1410 1
2 1064 1089 1
3 822 177
3 207 17
1 778 1433 110366 1
1 1187 1392 173818 1
3 550 14
2 715 1075 1
2 746 1417 1
1 464 1201 39231 1
2 331 626 1
1 538 990 218855 1
3 127 13
3 1444 9
3 549 22
2 394 573 1
2 1365 1439 1
3 1176 44
3 791 12
2 157 390 1
3 519 7
3 70 3
2 296 1262 1
1 299 326 701 1
2 144 557 1
1 399 1337 155826 1
3 65 2
3 355 11
2 124 904 1
2 629 1427 1
1 709 988 34919 1
1 792 918 111562 1
1 424 1122 116687 1
3 464 2
3 420 16
3 511 4
1 470 512 126491 1
2 884 1190 1
2 145 1358 1
2 956 1450 1
2 46 786 1
3 530 9
2 32 677 1
1 681 1425 194425 1
2 301 1011 1
2 65 274 1
3 591 7
1 543 596 55394 1
3 463 2
1 631 1042 155290 1
2 679 846 1
2 463 1245 1
3 226 7
1 284 548 26854 1
1 292 629 159497 1
1 14 442 40590 1
3 715 16
3 700 3
3 1368 3
3 1279 16
2 89 208 1
1 411 1235 44114 1
2 1233 1346 1
2 1150 1411 1
1 590 1210 124744 1
3 1021 3
1 924 1083 164395 1
2 136 287 1
2 686 811 1
1 77 277 103056 1
1 1076 1340 166148 1
2 715 1172 1
2 232 1321 1
1 1287 1384 61681 1
1 445 950 175075 1
2 185 810 1
2 205 981 1
3 502 4
2 35 473 1
2 636 1417 1
2 43 768 1
1 727 752 22217 1
2 369 1062 1
3 439 4
2 617 1161 1
3 127 7
2 944 1302 1
2 1278 1387 1
3 1263 15
3 665 23
2 335 563 1
2 568 1161 1
2 478 1177 1
2 16 829 1
1 809 1396 24300 1
2 9 757 1
1 503 590 87986 1
3 997 5
2 683 1450 1
1 348 586 99353 1
2 61 546 1
2 1053 1222 1
2 762 965 1
3 444 2
3 1429 5
3 441 3
3 503 1
1 466 1338 170370 1
2 311 497 1
3 1203 9
3 856 72
2 301 1426 1
3 1075 5
2 62 476 1
2 91 1071 1
2 880 1061 1
1 633 1326 38674 1
1 756 1248 233183 1
1 753 772 91788 1
3 864 13
2 584 609 1
3 814 8
3 977 9
2 266 459 1
3 725 408
2 97 371 1
1 860 1409 78800 1
2 807 986 1
1 292 415 172950 1
2 134 1230 1
1 436 910 175417 1
3 505 1
3 1447 6
3 621 38
2 64 1049 1
3 397 2
2 221 840 1
3 144 1
1 1244 1290 142919 1
2 574 801 1
3 1023 4
2 508 728 1
1 417 1250 236727 1
2 422 593 1
1 47 196 188686 1
3 561 29
2 851 1384 1
3 6 1
2 858 1444 1
3 629 16
1 635 784 126477 1
3 208 245
1 444 1144 8746 1
2 250 963 1
2 323 773 1
1 1258 1398 68733 1
2 582 1053 1
2 634 907 1
3 697 14
3 991 2
3 319 2
1 488 861 232725 1
3 1106 10
1 490 513 107890 1
2 561 761 1
1 380 780 224063 1
3 427 1
2 1016 1204 1
2 804 955 1
1 137 706 18302 1
3 27 2
1 145 750 128236 1
1 989 1230 170723 1
3 940 8
2 403 1146 1
3 1020 5
3 334 3
1 124 496 214544 1
1 228 1167 68461 1
2 47 659 1
1 915 1115 126587 1
2 836 979 1
1 1140 1291 135418 1
3 125 4
3 13 1
2 12 543 1
2 1242 1302 1
3 741 1
3 470 1
2 997 1135 1
2 457 676 1
1 170 1061 81751 1
3 29 3
3 256 12
1 153 1444 208872 1
2 175 1301 1
1 855 1449 70850 1
3 777 4
1 38 951 64263 1
1 1043 1082 132897 1
1 991 1094 68352 1
1 801 1201 129765 1
2 1071 1285 1
2 1105 1420 1
2 261 1261 1
2 47 335 1
2 61 152 1
3 1150 10
1 8 547 1695 1
1 1241 1351 211492 1
2 901 936 1
2 131 281 1
2 391 1397 1
3 946 10
1 238 945 219572 1
3 1431 314
3 452 10
3 1209 5
2 431 938 1
3 347 7
2 1172 1228 1
1 999 1436 11902 1
1 432 1036 65867 1
1 168 775 28268 1
1 865 968 158281 1
1 599 1057 99964 1
1 30 531 70647 1
3 1200 152
2 710 1431 1
2 943 949 1
1 725 1298 149765 1
3 1225 14
2 163 462 1
3 39 3
1 982 1302 123523 1
3 999 2
1 524 1048 210861 1
2 588 1164 1
2 529 609 1
1 980 1164 5598 1
1 204 1215 50997 1
1 220 855 77264 1
3 1344 7
3 238 1
2 845 1159 1
2 816 1030 1
3 1365 209
2 404 1358 1
3 536 17
2 661 1213 1
2 583 953 1
3 819 28
1 701 1446 232 1
2 21 690 1
2 150 1092 1
3 713 13
1 471 1195 85071 1
3 466 4
1 19 316 30408 1
2 28 860 1
3 1349 7
3 1216 8
3 563 9
2 589 709 1
3 1051 3
2 140 659 1
2 993 1136 1
1 1086 1303 235806 1
3 795 22
2 705 1355 1
3 764 3
3 1455 1
2 571 1436 1
3 622 11
2 185 640 1
1 147 1264 66853 1
2 403 589 1
1 486 570 4821 1
1 30 114 130554 1
2 27 425 1
1 503 673 174066 1
3 965 29
1 321 1276 125854 1
2 852 1379 1
1 245 653 90564 1
1 933 1048 43976 1
3 386 18
2 408 1002 1
*/

Compilation message (stderr)

foodcourt.cpp: In function 'void push_lazy(ll, ll, ll)':
foodcourt.cpp:211:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<lazy_query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  211 |         for (ll j = 0; j < lazy_add[root].size(); j ++)
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:216:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<lazy_query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |         for (ll j = 0; j < lazy_rem[root].size(); j ++)
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:226:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<lazy_query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |         while(j1 < lazy_add[root].size() && j2 < lazy_rem[root].size())
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:226:48: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<lazy_query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |         while(j1 < lazy_add[root].size() && j2 < lazy_rem[root].size())
      |                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:240:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<lazy_query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  240 |         while(j1 < lazy_add[root].size())
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:246:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<lazy_query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  246 |         while(j2 < lazy_rem[root].size())
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11