Submission #637358

#	Time	Username	Problem	Language	Result	Execution time	Memory
637358		MohamedFaresNebili	Teams (IOI15_teams)	C++14	0 / 100	4077 ms	24948 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];
                for(int l = 0; l < 4 * M; l++) ST[l] = 0;
                for(int l = 0; l < N; l++) {
                    int U = arr[l].first, V = arr[l].second;
                    for(int i = 0; i < M; i++) {
                        if(K[i] >= U && K[i] <= V) {
                            update(1, 0, M - 1, i, 1);
                            adj[l].push_back(i);
                        }
                    }
                }
                int res = 1; vector<bool> vis(N, 0);
                for(int i = 0; i < M; i++) {
                    int cur = 0; int l = query(1, 0, M - 1);
                    update(1, 0, M - 1, l, 4 * N);
                    for(int j = 0; j < N && cur < K[l]; j++) {
                        if(vis[j]) continue;
                        int U = arr[j].first, V = arr[j].second;
                        if(K[l] >= U && K[l] <= V) {
                            cur++, vis[j] = 1;
                            for(auto u : adj[j]) {
                                update(1, 0, M - 1, u, -1);
                            }
                        }
                    }
                    res &= (cur == 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