Submission #637361

#	Time	Username	Problem	Language	Result	Execution time	Memory
637361		MohamedFaresNebili	Teams (IOI15_teams)	C++14	0 / 100	4098 ms	27020 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"
 
            using namespace std;
 
            const int INF = INT32_MAX;
            const int batch = 750;
 
            vector<pair<int, int>> arr;
            int ST[800005];
 
            void init(int N, int A[], int B[]) {
                for(int i = 0; i < N; i++) {
                    int U = A[i], V = B[i];
                    arr.push_back({U, V});
                }
            }
            void update(int v, int l, int r, int p, int val) {
                if(l == r) {
                    ST[v] += val;
                    return;
                }
                int md = (l + r) / 2;
                if(p <= md) update(v * 2, l, (l + r) / 2, p, val);
                else update(v * 2 + 1, (l + r) / 2 + 1, r, p, val);
                ST[v] = min(ST[v * 2], ST[v * 2 + 1]);
            }
            int query(int v, int l, int r) {
                if(l == r) return l;
                if(ST[v * 2] <= ST[v * 2 + 1])
                    return query(v * 2, l, (l + r) / 2);
                return query(v * 2 + 1, (l + r) / 2 + 1, r);
            }
 
            int can(int M, int K[]) {
                int N = arr.size(); vector<int> adj[N];
                vector<int> order(N, 0);
                for(int l = 0; l < N; l++) {
                    order[l] = l;
                    int U = arr[l].first, V = arr[l].second;
                    for(int i = 0; i < M; i++)
                        if(K[i] >= U && K[i] <= V)
                            adj[l].push_back(i);
                }
                vector<int> cur(M, 0); int res = 1;
                sort(order.begin(), order.end(), [&](int A, int B) { return adj[A].size() < adj[B].size(); });
                for(int l = 0; l < N; l++) {
                    int i = order[l];
                    for(auto u : adj[i]) {
                        if(cur[u] < K[u]) { cur[u]++; break; }
                    }
                }
                for(int l = 0; l < M; l++)
                    res &= (cur[l] == K[l]);
                ///cout << res << "\n";
                return res;
            }

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:36:33: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   36 |                 int N = arr.size(); vector<int> adj[N];
      |                         ~~~~~~~~^~

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23