제출 #607605

#제출 시각아이디문제언어결과실행 시간메모리
607605Ronin13코끼리 (Dancing Elephants) (IOI11_elephants)C++14
100 / 100
4570 ms19184 KiB
#include "elephants.h" #include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define f first #define s second #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define epb emplace_back using namespace std; int n; int l; vector <vector <int> > a; vector <vector <pii> >bl(15001); vector <int> vec; int blsize; vector <int> le,ri; multiset <int> st; void process(int ind){ bl[ind].resize(a[ind].size()); int x = bl[ind].size(); if(x == 0) return; bl[ind][x - 1] = {0, a[ind][x - 1]}; int cur = x; for(int i = x - 2; i >= 0; i--){ while(a[ind][cur - 1] > a[ind][i] + l){ cur--; } if(cur == x){ bl[ind][i] = {0, a[ind][i]}; } else{ bl[ind][i] = {bl[ind][cur].f + 1, bl[ind][cur].s}; } } // cout << 1; } void er(int x){ st.erase(st.find(x)); for(int i = 0; i < le.size(); i++){ if(le[i] <= x && ri[i] >= x){ for(int j = 0; j < a[i].size(); j++){ if(a[i][j] == x) { a[i].erase(a[i].begin() + j); break; } } //for(int to : a[i]) cout << to << ' '; process(i); break; } } // cout << 1; } void in(int x){ st.insert(x); for(int i = 0; i < le.size(); i++){ if(le[i] <= x && ri[i] >= x){ a[i].pb(x); for(int j = a[i].size() - 2; j >= 0; j--){ if(a[i][j] < x) break; swap(a[i][j], a[i][j + 1]); } // for(int to : a[i]) cout << to << ' '; process(i); break; } } // cout << 1; } int A[150001]; void init(int N, int L, int x[]) { n = N; l = L; blsize = sqrt(n); for(int i = 0; i < n; i++) A[i] = x[i]; for(int i = 0; i < n; i++) st.insert(x[i]); } void init1(){ vector <int> cur; le.clear(); a.clear(); ri.clear(); for(int to : st){ cur.pb(to); if(cur.size() == blsize) {a.pb(cur), ri.pb(cur.back()), cur.clear(); if(le.empty()) le.pb(0); else le.pb(ri[ri.size() - 2] + 1);} } if(!cur.empty()){ a.pb(cur), ri.pb(cur.back()), cur.clear(); if(ri.size() > 1){ le.pb(ri[ri.size() - 2]); } else le.pb(0); } ri.back() = INT_MAX; for(int i = 0; i < a.size(); i++) process(i); } int getans(){ int ans = 0; int cur = 0; int nx = a[0][0]; for(int i = 0; i < a.size(); i++){ int L = -1, R = a[i].size(); while(L + 1 < R){ int m = (L + R) / 2; if(a[i][m] >= nx) R = m; else L = m; } if(R == a[i].size()) continue; ans += bl[i][R].f + 1; //cout << l << "\n"; nx = bl[i][R].s + l + 1; } //cout << 1; return ans; } int cnt = 0; int update(int i, int y) { er(A[i]); A[i] = y; in(A[i]); if(cnt % blsize == 0) init1(); cnt++; return getans(); }

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

elephants.cpp: In function 'void er(int)':
elephants.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0; i < le.size(); i++){
      |                    ~~^~~~~~~~~~~
elephants.cpp:46:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for(int j = 0; j < a[i].size(); j++){
      |                            ~~^~~~~~~~~~~~~
elephants.cpp: In function 'void in(int)':
elephants.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < le.size(); i++){
      |                    ~~^~~~~~~~~~~
elephants.cpp: In function 'void init1()':
elephants.cpp:95:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |         if(cur.size() == blsize) {a.pb(cur), ri.pb(cur.back()), cur.clear();
      |            ~~~~~~~~~~~^~~~~~~~~
elephants.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0; i < a.size(); i++) process(i);
      |                    ~~^~~~~~~~~~
elephants.cpp: In function 'int getans()':
elephants.cpp:115:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i = 0; i < a.size(); i++){
      |                    ~~^~~~~~~~~~
elephants.cpp:123:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         if(R == a[i].size()) continue;
      |            ~~^~~~~~~~~~~~~~
elephants.cpp:113:9: warning: unused variable 'cur' [-Wunused-variable]
  113 |     int cur = 0;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...