제출 #70749

#제출 시각아이디문제언어결과실행 시간메모리
70749Navick팀들 (IOI15_teams)C++17
0 / 100
304 ms20188 KiB
#include <bits/stdc++.h> #include "teams.h" #define pb push_back #define pii pair<int, int> #define pb push_back using namespace std; typedef long long ll; const int maxN = 1e5 + 10, LOG = 19; vector <int> qu[maxN], lefts; int cnt[maxN], n, lf[maxN], rg[maxN]; int seg[LOG][maxN], perm[maxN]; bool cmp(int i, int j) { return make_pair(lf[i], rg[i]) < make_pair(lf[j], rg[j]); } void build(int lg = 0, int s = 0, int e = n) { if(e - s < 2) { int p = perm[s]; seg[lg][s] = rg[p]; return ; } int mid = (s + e)/2; build(lg + 1, s, mid); build(lg + 1, mid, e); merge(seg[lg + 1] + s, seg[lg + 1] + mid, seg[lg + 1] + mid, seg[lg + 1] + e, seg[lg] + s); return ; } int get(int lg, int L, int R, int ql, int qr, int s = 0, int e = n) { if(L<=s && e<=R) { int idl = lower_bound(seg[lg] + s, seg[lg] + e, ql) - seg[lg]; int idr = upper_bound(seg[lg] + s, seg[lg] + e, qr) - seg[lg]; return idr - idl; } if(L>=e || s>=R) return 0; int mid = (s + e)/2; return get(lg + 1, L, R, ql, qr, s, mid) + get(lg + 1, L, R, ql, qr, mid, e); } void init(int N, int A[], int B[]) { n = N; for (int i=0; i<n; i++) lf[i] = A[i], rg[i] = B[i], lefts.pb(lf[i]); sort(lefts.begin(), lefts.end()); for (int i=0; i<n; i++) perm[i] = i; sort(perm, perm + n, cmp); build(); } vector <int> vc; int can(int m, int k[]) { //for (auto x : lefts) cout << x << ' '; cout << endl; vc.clear(); for (int i=0; i<m; i++) vc.pb(k[i]), cnt[k[i]] ++; sort(vc.begin(), vc.end()); vc.resize(unique(vc.begin(), vc.end()) - vc.begin()); int sz = (int) vc.size(), last = 0; ll s = 0, p = 0; for (int i=0; i<sz; i++) { int x = vc[i]; int pl = upper_bound(lefts.begin(), lefts.end(), last) - lefts.begin(); int pr = lower_bound(lefts.begin(), lefts.end(), x + 1) - lefts.begin(); int g1 = get(0, pl, pr, x , n); pl = 0; pr = lower_bound(lefts.begin(), lefts.end(), last + 1) - lefts.begin(); int g2 = get(0, pl, pr, last, x - 1); if(p >= g2) p -= g2; else s -= g2 - p, p = 0; s += g1; if(s < 1LL * cnt[x] * x) { for (int j=0; j<m; j++) cnt[k[j]] --; return 0; } s -= 1LL * cnt[x] * x; p += 1LL * cnt[x] * x; last = vc[i]; //cout << i << " --> " << s << ',' << p << endl; //cout << cnt[i] << endl; } for (int i=0; i<m; i++) cnt[k[i]] --; return 1; }

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'int get(int, int, int, int, int, int, int)':
teams.cpp:44:55: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int idl = lower_bound(seg[lg] + s, seg[lg] + e, ql) - seg[lg];
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
teams.cpp:45:55: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int idr = upper_bound(seg[lg] + s, seg[lg] + e, qr) - seg[lg];
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:83:58: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int pl = upper_bound(lefts.begin(), lefts.end(), last) - lefts.begin();
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
teams.cpp:84:59: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int pr = lower_bound(lefts.begin(), lefts.end(), x + 1) - lefts.begin();
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
teams.cpp:89:58: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   pr = lower_bound(lefts.begin(), lefts.end(), last + 1) - lefts.begin();
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...