Can someone share a non BIT or seg tree AC soln. using sets or ordered sets? I want to know how binary search can be used to find an x that is not covered by a rook in the sub-rectangle having x coordinates ranging from x1 to x2 and the same for y? I want to know why the following submission below gives WA on pretest 3 to problem C :

#include <iostream>
#include <vector>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
void solve() {
    ordered_set xoset;
    ordered_set yoset;
    int n, q, qt, x, y, x1, y1, x2, y2;
    cin >> n >> q;
    for (int i = 0; i < q; i++) {
        cin >> qt;
        if (qt == 1) {
            cin >> x >> y;
            xoset.insert(x);
            yoset.insert(y);
        } else if (qt == 2) {
            cin >> x >> y;
            xoset.erase(xoset.find(x));
            yoset.erase(yoset.find(y));
        } else {
            cin >> x1 >> y1 >> x2 >> y2;
            int x_diff = xoset.order_of_key(x2 + 1) - xoset.order_of_key(x1);
            int y_diff = yoset.order_of_key(y2 + 1) - yoset.order_of_key(y1);
            // cout << x_diff << " " << y_diff << endl;
            if (x_diff == (x2 - x1 + 1) or y_diff == (y2 - y1 + 1)) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
        }
    }
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++) {
        // cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}

Requesting help from the community to understand this, please!

An athlete is lifting weights. The maximum capacity of the barbell is maxCapacity. Each barbell plate has a weight, weight[i]. Determine the maximum weight of plates that can be added to the barbell without exceeding maxCapacity.

Example

weights = [7, 1, 5, 6, 2]

maxCapacity = 7

There are 3 ways to reach the maximum weight: {7}, {1, 6} and {2, 5}. Other combinations are either more or less than 7 combined weight. Return 7.

Constraints

1 ≤ n ≤ 42 1 ≤ maxCapacity ≤ 10^9 1 ≤ weights[i][ ]≤ 10^9

Solution for 1e6 or 10^6 constraints:

int weightCapacity(vector<int> &weights, int maxCapacity) {
    
        int n = weights.size();
        vector<bool> dp(maxCapacity+1, false);
        dp[0] = true;
        int maxW = 0;
        for(int i = 0; i < n; ++i)
        {
    
            for(int j = maxCapacity-weights[i]; j>=0; --j)
            {
    	// Traversal in reverse order , The new state does not interfere with the old state to be traversed 
                if(dp[j])// j  Weight status exists 
                {
    
                    dp[j+weights[i]] = true;
                    maxW = max(maxW, j+weights[i]);
                }
            }
        }
        return maxW;
    }

How can we use binary search here for the tighter constraints. I understand the monotonicity but how do we check whether such a subsequence exists in the array that sums up to the mid weight?

In these times, we have clearly noticed the lack of decency of comments and posts, a lot of them containing political motivation and racial or social hatred. Let's give an option to report posts and lets say if a 100 users report a comment, then the comment should be immediately removed, if less than 100 reports are there, someone must verify the contents of the post or comment and then take a decision.

It's sad to even suggest this on a platform which only few years ago, had so informational and quality posts, but now it seems to have turned into newsforces! An option to delete posts or comments must be given too, if at all we want to keep it fair and give a chance to such people to atone, but I do not suggest rolling back the contribution. Let's have the right to report/flag offensive posts and to delete our own blogs, if we so deem fit!

Most of the times people are worried more about the problems that they solved towards the end of the contest... And contests after which the system testing takes a long time, we can't wait to have them judged. So, should we have system testing, but in the order of LIFO?

MikeMirzayanov I would like to remove my data (if used at all, and I urge other programmers too), in training the AI competing in the next Div 2 round. I don't wish such kind of programs emulating human ingenuity in the hands of evil corporations or in the possession of such monstrous AI, or even in the hands of cheaters might use them to cheat. There is not one good reason for this thing to exist, let alone participate in such competitions. I don't want to participate as well in such competitions that might aid this AI. PLEASE STOP BEFORE IT'S TOO LATE. WHY DONT HUMANS LEARN EVEN AFTER DISASTER'S AS COVID. SOMEDAY THIS POST MIGHT BE THE REMEMBERED AS THE ONE THAT TRIED TO STOP ALL THIS MADNESS!

IT'S FINE THAT SOME PEOPLE WANT TO WITNESS THE WONDERS OF AI, BUT I DONT WANT MY CODE CAUSING MILLIONS OF JOB LOSSES SOMEDAY AND A LOT OF GRIEF FOR THOSE PEOPLE!

This question was asked for an Amazon hackathon coding round held almost two weeks ago which is over now. So I am assuming its alright to discuss the problem (rephrased) now. Please let me know if this is a common problem of priority queues/heaps which I am again assuming might be useful for a solution. Hoping for meaningful approaches and solutions from the codeforces community, which is truly helpful and supportive!

The Problem Statement:

A chef has n orders lined up. The waiting time penalty before an order starts getting processed is k. And for each order a corresponding processing time t is given (in minutes) along with its order id. The earning per order is c times the time taken to process the order. Find out the profits earned for each order from 1 to n and print them in order of the input. The order is free if the profits are negative for that order i.e. the profits is max(0,profit).

The following rules are used for processing the orders:

1. Pick the order which arrives first. The chef can process only one order at a time.

2. Among the orders already arrived, pick the one with the least processing time.

Input Format:

First the number of test cases T is given. Then T test cases follow. Each test case consists of n (the number of orders),c (the cost per minute it takes to process any order, which is same for all orders) and k (the waiting time penalty per minute, the chef faces once an order has arrived and is there in the "waiting to be processed queue"). Then in the following n lines an order with its arrival time and processing time is given. The order id of the first of these n lines is 1, the order id of the 2nd order is 2, and so on till the nth line has the order id n. Note that the input may or may not be sorted by the arrival time i.e. order 3 may arrive earlier than order 2 and so on.

Output Format: For each test case, print in a single line the profits earned for orders 1 to n, respectively.

Constraints:

1<=T<=10 ; 1<=n<=10^5 ; 1<=order arrival time, order processing time <= 10^9 ; 1<=k<=100 ; 1<=c<=10^4 ; Time limit: 1 second per test case

Example :

Input:

1
3 10 16
1 2
2 3
3 1

Explanation: The number of test cases T = 1. Number of orders n = 3. Processing cost per order per minute i.e. c = 10. Penalty cost for an order already arrived but in the waiting queue per minute of waiting i.e. k = 1. Then the list of orders follow. Order 1 arrives at time t=1. the chef does nothing from t=0 to t=1. Since he has to pick up the order which arrived first his profit earned for order 1 would be would be processing time*c — k*waiting time. Since the order was processed immediately as it came, the waiting time would be 0 for order 1. Hence, profit of order 1 = 2*10 — 16*0= 20. Now the time t=1+2=3 . Therefore both orders 2 and 3 have arrived and are in the waiting queue. But chef chooses order 3 to be processed first since it has less processing time. Therefore profit for order 3 is 1*10-16*0=10, as the order 3 was processed the moment it came. Now the time t=3+1=4 and the last order 2 is taken up which has been waiting for 4-2=2 minutes. Therefore the profit earned for order 2 = 3*10 — 16*2= 30 — 32 = -2. Therefore the order is free or profit = 0.

Output: 20 0 10

Any help would be appreciated. Here are the numerous approaches I took. First I did a simple sorting by arrival time and then used a map to get me the ones using upper bound and lower bound the items that would be in my absolute time range i.e. would have arrived by then and then used those to get the minimum processing time to process. I would keep doing that till all my orders would have been processed. The same approach I tried using priority queue and heap but failed for the case when the arrival time of say the last order was much ahead of the last order processed (which was already finished processing by then) and my range finding of orders failed and the program just halted in an infinite loop kind of situation. If I put an absolute time outer loop the time constraint would not be met. I am guessing an O(n log n) algorithm is needed to solve this question. Can anyone suggest efficient and easy approaches or codes?