제출 #542114

#제출 시각아이디문제언어결과실행 시간메모리
542114wildturtle팀들 (IOI15_teams)C++17
0 / 100
4067 ms94244 KiB
#include "teams.h" #include<bits/stdc++.h> #define ll long long #define f first #define sc second #define pb push_back using namespace std; int a,b,c,d,i,e,f,g,n,m,l; int tree[4*500005],lef[3*500005],righ[4*500005]; int root[500005],k[500005],dp[500005]; int snode,prevroot,tim; set <int> st1; set < pair <int,int> > st; vector <int> v[500005]; void build(int node,int le,int ri) { if(le==ri) { tree[node]=0; return; } snode++; lef[node]=snode; build(snode,le,(le+ri)/2); snode++; righ[node]=snode; build(snode,(le+ri)/2+1,ri); tree[node]=tree[lef[node]]+tree[righ[node]]; } void update(int node,int prevnode,int le,int ri,int idx) { if(ri<idx || le>idx) return; if(le==ri) { tree[node]=tree[prevnode]+1; return; } if(idx<=(le+ri)/2) { snode++; lef[node]=snode; righ[node]=righ[prevnode]; update(snode,lef[prevnode],le,(le+ri)/2,idx); } else { snode++; righ[node]=snode; lef[node]=lef[prevnode]; update(snode,righ[prevnode],(le+ri)/2+1,ri,idx); } tree[node]=tree[lef[node]]+tree[righ[node]]; } int getans(int node,int start,int end,int le,int ri) { if(ri<start || le>end) return 0; if(start<=le && ri<=end) return tree[node]; return getans(lef[node],le,(le+ri)/2,start,end)+getans(righ[node],(le+ri)/2+1,ri,start,end); } int Z(int x,int y) { return getans(root[y],y,n,1,n)-getans(root[x],y,n,1,n); } int go(int x,int y) { int le=k[b]+1; int ri=n; int ans=0; while(le<=ri) { int mid=(le+ri)/2; if(dp[a]-dp[b]<-(getans(root[k[b]],mid,n,1,n)-getans(root[k[a]],mid,n,1,n))) { ans=mid; ri=mid-1; } else le=mid+1; } return ans; } void add(int x) { if(!st1.size()) { st1.insert(x); return; } int pat=*(--st1.end()); st1.insert(x); tim=go(pat,x); if(tim) st.insert({tim,x}); } void del(int x) { if(!st1.count(x)) return; st1.erase(x); if(!st1.size()) return; int pat=-1; int did=-1; if(*st1.begin()<x) pat=*(--st1.upper_bound(x)); if(st1.upper_bound(x)!=st1.end()) did=*st1.upper_bound(x); if(did!=-1) { tim=go(x,did); if(tim) st.erase({tim,did}); } if(pat!=-1) { tim=go(pat,x); if(tim) st.erase({tim,x}); } if(did!=-1 && pat!=-1) { tim=go(pat,did); if(tim) st.insert({tim,did}); } } int can(int M, int K[]) { st.clear(); st1.clear(); m=M; for(int i=m;i>=1;i--) { k[i]=K[i-1]; dp[i]=0; } int sum=0; for(int i=1;i<=m;i++) { sum+=k[i]; } if(sum>n) return 0; sort(k+1,k+1+m); dp[0]=0; add(0); for(int i=1;i<=m;i++) dp[i]=1e9; for(int i=1;i<=m;i++) { while(st.size()) { multiset < pair <int,int> > :: iterator it = st.begin(); if((*it).f<=k[i]) del((*it).sc); else break; } int idx=*(--st1.end()); dp[i]=dp[idx]+Z(k[idx],k[i])-k[i]; if(dp[i]<0) return 0; add(i); } return 1; } void init(int N, int A[], int B[]) { n=N; for(int i=0;i<N;i++) { v[A[i]].pb(B[i]); } snode=1; root[0]=snode; 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++) { snode++; root[i]=snode; update(root[i],prevroot,1,n,v[i][j]); prevroot=root[i]; } } }

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

teams.cpp: In function 'int go(int, int)':
teams.cpp:52:12: warning: unused parameter 'x' [-Wunused-parameter]
   52 | int go(int x,int y) {
      |        ~~~~^
teams.cpp:52:18: warning: unused parameter 'y' [-Wunused-parameter]
   52 | int go(int x,int y) {
      |              ~~~~^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:96:13: warning: declaration of 'i' shadows a global declaration [-Wshadow]
   96 |     for(int i=m;i>=1;i--) {
      |             ^
teams.cpp:8:13: note: shadowed declaration is here
    8 | int a,b,c,d,i,e,f,g,n,m,l;
      |             ^
teams.cpp:101:10: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  101 |  for(int i=1;i<=m;i++) {
      |          ^
teams.cpp:8:13: note: shadowed declaration is here
    8 | int a,b,c,d,i,e,f,g,n,m,l;
      |             ^
teams.cpp:108:10: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  108 |  for(int i=1;i<=m;i++) dp[i]=1e9;
      |          ^
teams.cpp:8:13: note: shadowed declaration is here
    8 | int a,b,c,d,i,e,f,g,n,m,l;
      |             ^
teams.cpp:109:10: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  109 |  for(int i=1;i<=m;i++) {
      |          ^
teams.cpp:8:13: note: shadowed declaration is here
    8 | int a,b,c,d,i,e,f,g,n,m,l;
      |             ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:124:13: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  124 |     for(int i=0;i<N;i++) {
      |             ^
teams.cpp:8:13: note: shadowed declaration is here
    8 | int a,b,c,d,i,e,f,g,n,m,l;
      |             ^
teams.cpp:130:10: warning: declaration of 'i' shadows a global declaration [-Wshadow]
  130 |  for(int i=1;i<=N;i++) {
      |          ^
teams.cpp:8:13: note: shadowed declaration is here
    8 | int a,b,c,d,i,e,f,g,n,m,l;
      |             ^
teams.cpp:133:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         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...