제출 #898503

#제출 시각아이디문제언어결과실행 시간메모리
898503DenkataSegments (IZhO18_segments)C++14
컴파일 에러
0 ms0 KiB
#include<bits/stdc++.h> using namespace std; const int maxn = 2e5+3; const int crit = 2000; int i,j,p,q,n,m,k,L,R,A,B,lans,id,lb[maxn],rb[maxn],block[maxn],minlen[maxn],t,curlen; vector < pair <int,int> > cur,all; vector < pair <int,int> > levi[100],desni[100];//n/crit int removed[maxn]; void insert(int l,int r,int nom) { cur.push_back({r-l+1,nom}); if(cur.size()==crit) { vector <pair <int,int>> neww; for(i=0; i<=all.size()/crit+2; i++) levi[i].clear(),desni[i].clear(),minlen[i] = -1; for(auto i:cur) neww.push_back(i); for(auto i:all) neww.push_back(i); cur.clear(); all.clear(); for(auto i:neww) { if(!removed[i.second]) all.push_back(i); } ///build the structure sort(all.rbegin(),all.rend()); int bl = 0; int br = 0; int Min = INT_MAX; for(auto i:all) { levi[bl].push_back({lb[i.second],i.second}); desni[bl].push_back({rb[i.second],i.second}); Min = min(Min,i.first); block[i.second] = bl; br++; if(br==crit) { minlen[bl] = Min; Min = INT_MAX; bl++; br = 0; } } for(i=0; i<=all.size()/crit+2; i++) { if(levi[i].empty())break; sort(levi[i].begin(),levi[i].end()); sort(desni[i].begin(),desni[i].end()); } } } void remove(int id) { removed[id] = true; if(block[id]==-1) return ; p = block[id]; vector < pair <int,int> > newws; for(auto i:levi[p]) if(i.second!=id)newws.push_back(i); levi[p] = newws; newws.clear(); for(auto i:desni[p]) if(i.second!=id)newws.push_back(i); desni[p] = newws; block[id] = -1; } int solve(int l,int r,int k) { int ans = 0; for(auto i:cur) { if(removed[i.second]) continue; //cout<<lb[i.second]<<" "<<rb[i.second]<<" "<<l<<" "<<r<<" "<<k<<endl; if(min(rb[i.second],r)-max(lb[i.second],l)+1>=k) ans++; } for(i=0; i<=all.size()/crit+1; i++) { if(minlen[i]==-1)break; if(minlen[i]<k) { ///iterative check j = i; for(auto i:levi[j]) { if(removed[i.second]) continue; if(min(rb[i.second],r)-max(lb[i.second],l)+1>=k) ans++; } break; } ans+=levi[i].size(); p = 0; ///indexed from 0 p += upper_bound(desni[i].begin(),desni[i].end(), make_pair(l+k-2,1e7))-desni[i].begin(); p += levi[i].size()-(lower_bound(levi[i].begin(),levi[i].end(), make_pair(r-k+2,-1))-levi[i].begin()); ans-=p; } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>t; for(i=0; i<=n; i++) block[i] = -1,minlen[i] = -1; lans = 0; while(n--) { int type; cin>>type; if(type==1) { cin>>A>>B; L = A^(t*lans); R = B^(t*lans); if(L>R)swap(L,R); curlen++; lb[curlen] = L; rb[curlen] = R; insert(L,R,curlen); } else if(type==2) { cin>>id; remove(id); } else { cin>>A>>B>>k; L = A^(t*lans); R = B^(t*lans); if(L>R)swap(L,R); lans = solve(L,R,k); cout<<lans<<endl; } } return 0; } /** 6 1 1 1 2 3 2 4 2 1 3 5 3 2 3 1 2 1 3 0 3 1 6 0 1 3 10 1 3 5 3 6 10 6 2 1 1 3 10 3 6 4 2 */

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

segments.cpp: In function 'void insert(int, int, int)':
segments.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for(i=0; i<=all.size()/crit+2; i++)
      |                  ~^~~~~~~~~~~~~~~~~~~
segments.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(i=0; i<=all.size()/crit+2; i++)
      |                  ~^~~~~~~~~~~~~~~~~~~
segments.cpp: In function 'int solve(int, int, int)':
segments.cpp:90:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(i=0; i<=all.size()/crit+1; i++)
      |              ~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_less_iter::operator()(_Value&, _Iterator) const [with _Value = const std::pair<int, double>; _Iterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >]':
/usr/include/c++/10/bits/stl_algo.h:2061:14:   required from '_ForwardIterator std::__upper_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Tp = std::pair<int, double>; _Compare = __gnu_cxx::__ops::_Val_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:2096:32:   required from '_FIter std::upper_bound(_FIter, _FIter, const _Tp&) [with _FIter = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Tp = std::pair<int, double>]'
segments.cpp:109:79:   required from here
/usr/include/c++/10/bits/predefined_ops.h:96:22: error: no match for 'operator<' (operand types are 'const std::pair<int, double>' and 'std::pair<int, int>')
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)'
 1096 |     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, double>' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)'
 1104 |     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, double>' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from segments.cpp:1:
/usr/include/c++/10/bits/regex.h:1075:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
 1075 |     operator<(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1075:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, double>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from segments.cpp:1:
/usr/include/c++/10/bits/regex.h:1156:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)'
 1156 |     operator<(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1156:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, double>' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from segments.cpp:1:
/usr/include/c++/10/bits/regex.h:1249:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1249 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1249:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, double>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from segments.cpp:1:
/usr/include/c++/10/bits/regex.h:1323:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)'
 1323 |     operator<(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1323:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from segments.cpp:1:
/usr/include/c++/10/bits/regex.h:1417:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1417 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1417:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, double>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from segments.cpp:1:
/usr/include/c++/10/bits/regex.h:1492:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)'
 1492 |     operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1492:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from segments.cpp:1:
/usr/include/c++/10/bits/regex.h:1592:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1592 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1592:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, double>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:489:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
  489 |     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:489:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   deduced conflicting types for parameter '_T2' ('double' and 'int')
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:366:5: note: candidate: 'template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
  366 |     operator<(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:366:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note:   'const std::pair<int, double>' is not derived from 'const std::reverse_iterator<_Iterator>'
   96 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/stl_iterato