제출 #133128

#제출 시각아이디문제언어결과실행 시간메모리
133128Mahdi_Jfri팀들 (IOI15_teams)C++14
77 / 100
4126 ms524028 KiB
#include "teams.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int maxn = 5e5 + 20; const int sq = 200; const int maxb = 20; int dp[maxn] , n , l[maxn] , r[maxn]; int seg[maxb][maxn] , lpt[maxb][maxn] , rpt[maxb][maxn] , cnt[sq + 5][maxn]; void build(int s = 0 , int e = n , int h = 0) { if(e - s < 2) { seg[h][s] = l[s]; return; } int m = (s + e) / 2; build(s , m , h + 1); build(m , e , h + 1); int pt1 = s , pt2 = m , pt = s; while(pt != e) { if(pt2 == e || (pt1 < m && seg[h + 1][pt1] < seg[h + 1][pt2])) { lpt[h][pt] = pt1; if(pt2 == e) rpt[h][pt] = maxn; else rpt[h][pt] = pt2; seg[h][pt] = seg[h + 1][pt1++]; } else { rpt[h][pt] = pt2; if(pt1 == m) lpt[h][pt] = maxn; else lpt[h][pt] = pt1; seg[h][pt] = seg[h + 1][pt2++]; } pt++; } } inline int get(int r , int val , int s = 0 , int e = n , int h = 0) { int ans = 0; val = lower_bound(seg[h] + s , seg[h] + e , val) - seg[h]; if(val == e) return 0; while(1) { if(val >= maxn) return ans; if(e <= r) return ans + e - val; if(r <= s) return ans; int m = (s + e) / 2; if(r <= m) val = lpt[h][val] , e = m , h++; else { ans += max(0 , m - lpt[h][val]); val = rpt[h][val] , s = m , h++; } } } void init(int N, int a[], int b[]) { n = N; vector<pair<int , int> > tmp; for(int i = 0; i < n; i++) { l[i] = a[i] , r[i] = b[i]; tmp.pb({r[i] , -l[i]}); } sort(tmp.begin() , tmp.end()); for(int i = 0; i < n; i++) l[i] = -tmp[i].second , r[i] = tmp[i].first; build(); for(int i = 1; i <= sq; i++) { int pt = 0 , t = 0; for(int j = i; j <= n; j++) { while(pt < n && r[pt] <= j) t += (l[pt++] >= i); cnt[i][j] = t; } } } int p[maxn] , t[maxn]; int can(int m, int k[]) { sort(k , k + m); for(int i = 0; i < m; i++) t[k[i]] = 0; int sum = 0; for(int i = 1; i <= m; i++) { p[i] = k[i - 1]; sum += p[i]; if(sum > n) return 0; t[p[i]]++; } m = unique(p + 1 , p + m + 1) - p - 1; p[0] = 0; dp[0] = 0; for(int i = 1; i <= m; i++) { dp[i] = -1e9; int x = lower_bound(r , r + n , p[i]) - r; for(int j = i - 1; j >= 0; j--) { if(p[j] + 1 <= sq) dp[i] = max(dp[i] , dp[j] + cnt[p[j] + 1][p[i] - 1]); else dp[i] = max(dp[i] , dp[j] + get(x , p[j] + 1)); } dp[i] += t[p[i]] * p[i]; if(dp[i] + get(n , p[i] + 1) - n > 0) return 0; } return 1; }

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

teams.cpp: In function 'int get(int, int, int, int, int)':
teams.cpp:57:67: warning: declaration of 'r' shadows a global declaration [-Wshadow]
 inline int get(int r , int val , int s = 0 , int e = n , int h = 0)
                                                                   ^
teams.cpp:13:30: note: shadowed declaration is here
 int dp[maxn] , n , l[maxn] , r[maxn];
                              ^
teams.cpp:60:51: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  val = lower_bound(seg[h] + s , seg[h] + e , val) - seg[h];
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:133:36: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  m = unique(p + 1 , p + m + 1) - p - 1;
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:142:41: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int x = lower_bound(r , r + n , p[i]) - r;
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...