제출 #541128

#제출 시각아이디문제언어결과실행 시간메모리
541128lukameladze팀들 (IOI15_teams)C++14
21 / 100
4085 ms38448 KiB
#include "teams.h" #include <bits/stdc++.h> #define f first #define s second #define pb push_back using namespace std; const int N = 3e5 + 5; int tree[10*N],le_[10*N], ri_[10*N]; int cur,root[N],prevroot,dp[N],m,a[N],b[N],k[N],n,cnt; vector <int> v[N]; int merge(int a, int b) { return a + b; } void build(int node, int le, int ri) { // cout<<le<<" "<<ri<<" "<<node<<endl; if (le == ri) { tree[node] = 0; return ; } cur++; le_[node] = cur; cur++; ri_[node] = cur; int mid = (le + ri) / 2; build(le_[node],le,mid); build(ri_[node],mid + 1, ri); tree[node] = merge(tree[le_[node]], tree[ri_[node]]); } void update(int node, int le, int ri, int idx, int val) { if (le > idx || ri < idx) return ; if (le == ri) { //cout<<cur<<" "<<val<<endl; tree[cur] = tree[node] + val; //cout<<cur<<" "<<le<<" "<<ri<<" "<<tree[cur]<<endl; return ; } int mid = (le + ri) / 2; int x = cur; cur++; le_[x] = le_[node]; ri_[x] = ri_[node]; if (idx <= mid) { le_[x] = cur; } else ri_[x] = cur; update(le_[node], le,mid,idx,val); update(ri_[node], mid + 1, ri, idx,val); tree[x] = merge(tree[le_[x]], tree[ri_[x]]); //cout<<x<<" "<<le<<" "<<ri<<" "<<tree[x]<<endl; } int getans(int node, int le, int ri, int start, int end) { if (le > end || ri < start) return 0; if (le >= start && ri <= end) { return tree[node]; } int mid = (le + ri) / 2; return merge(getans(le_[node],le,mid,start,end), getans(ri_[node],mid + 1,ri,start,end)); } int can(int M, int K[]) { m = M; for (int i = 1; i <= m; i++) { dp[i] = 1e9; k[i] = K[i - 1]; } int sum = 0; for (int i = 1; i <= m; i++) { sum += k[i]; } if (sum > n) { return 0; } sort(k + 1, k + m + 1); dp[0] = 0; for (int i = 1; i <= m; i++) { for (int j = i - 1; j >= 0; j--) { // k[j]+1 -----> k[i] shualedshi >= k[i] cnt = getans(root[k[i]],1,n,k[i],n) - getans(root[k[j]],1,n,k[i],n); dp[i] = min(dp[i],dp[j] + cnt - k[i]); //cout<<i<<" "<<j<<" "<<dp[j]<<" "<<cnt<<endl; if (dp[i] < 0) { return 0; } } //cout<<i<<" "<<dp[i]<<endl; } return 1; } void init(int N, int A[], int B[]) { n = N; for (int i = 1; i <= n; i++) { a[i] = A[i - 1]; b[i] = B[i - 1]; v[a[i]].pb(b[i]); } cur = 1; root[0] = 1; build(1,1,n); for (int i = 1; i <= n; i++) { prevroot = root[i - 1]; root[i] = root[i - 1]; for (int j = 0; j < v[i].size(); j++) { cur++; root[i] = cur; update(prevroot, 1,n,v[i][j],1); prevroot = root[i]; } } dp[0] = 0; }

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

teams.cpp: In function 'int merge(int, int)':
teams.cpp:11:22: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   11 | int merge(int a, int b) {
      |                  ~~~~^
teams.cpp:9:39: note: shadowed declaration is here
    9 | int cur,root[N],prevroot,dp[N],m,a[N],b[N],k[N],n,cnt;
      |                                       ^
teams.cpp:11:15: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   11 | int merge(int a, int b) {
      |           ~~~~^
teams.cpp:9:34: note: shadowed declaration is here
    9 | int cur,root[N],prevroot,dp[N],m,a[N],b[N],k[N],n,cnt;
      |                                  ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:89:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   89 | void init(int N, int A[], int B[]) {
      |           ~~~~^
teams.cpp:7:11: note: shadowed declaration is here
    7 | const int N = 3e5 + 5;
      |           ^
teams.cpp:101:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for (int j = 0; j < v[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...