제출 #561341

#제출 시각아이디문제언어결과실행 시간메모리
561341fcmalkcinRectangles (IOI19_rect)C++17
0 / 100
151 ms302556 KiB
#include <bits/stdc++.h> using namespace std; #define ll int #define pll pair<ll,ll> #define ff first #define ss second #define pb push_back //#define endl "\n" mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); const ll maxn=2e3+5e2+10; //const ll maxn=50; const ll mod=1e9+7 ; const ll base=1e18; /// i believe myself /// goal 2/7 bool dd[maxn][maxn]; vector<pair<ll,pll>> adj[maxn]; vector<ll> fwt[maxn][maxn]; vector<ll> vt[maxn][maxn]; #include "rect.h" long long count_rectangles(vector<vector<ll>> a) { ll n=a.size(); ll m=a[0].size(); if (min(n,m)<=2) return 0; vector<pair<pll,ll>> vt; for (int i=1;i+1<n;i++) { stack<ll> st; vector<pll> vt1; for (int j=0;j<m;j++) { while (st.size()&&a[i][st.top()]<a[i][j]) st.pop(); if (st.size()) { ll h=st.top(); if (!dd[h][j]&&h+1<j) { dd[h][j]=1; vt.pb(make_pair(make_pair(h,j),i)); vt1.pb(make_pair(h,j)); } } st.push(j); } while (st.size()) st.pop(); for (int j=m-1;j>=0;j--) { while (st.size()&&a[i][st.top()]<a[i][j]) st.pop(); if (st.size()) { ll h=st.top(); if (!dd[j][h]&&j+1<h) { dd[j][h]=1; vt.pb(make_pair(make_pair(j,h),i)); vt1.pb(make_pair(j,h)); } } st.push(j); } for (auto p:vt1) dd[p.ff][p.ss]=false; } sort(vt.begin(),vt.end()); for (int i=0;i<vt.size();i++) { ll j=i+1; while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j].ss) j++; j--; auto p=vt[j].ff; p.ff++; p.ss--; ll l=vt[i].ss-1; ll r=vt[j].ss+1; adj[l].pb(make_pair(r,p)); i=j; } vt.clear(); for (int j=0;j<m;j++) { stack<ll> st; vector<pll> vt1; for (int i=0;i<n;i++) { while (st.size()&&a[st.top()][j]<a[i][j]) st.pop(); if (st.size()) { ll h=st.top(); if (!dd[h][i]&&h+1<i) { dd[h][i]=1; vt.pb(make_pair(make_pair(h,i),j)); vt1.pb(make_pair(h,i)); } } st.push(i); } while (st.size()) st.pop(); for (int i=0;i<n;i++) { while (st.size()&&a[st.top()][j]<a[i][j]) st.pop(); if (st.size()) { ll h=st.top(); if (!dd[i][h]&&i+1<h) { dd[i][h]=1; vt.pb(make_pair(make_pair(i,h),j)); vt1.pb(make_pair(i,h)); } } st.push(i); } for (auto p:vt1) dd[p.ff][p.ss]=false; } sort(vt.begin(),vt.end()); for (int i=0;i<vt.size();i++) { ll j=i+1; while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j].ss) j++; j--; ll l=vt[i].ss; ll r=vt[j].ss; auto p=vt[j].ff; i=j; } return -1; }

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

rect.cpp:15:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | const ll base=1e18;
      |               ^~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i=0;i<vt.size();i++)
      |                  ~^~~~~~~~~~
rect.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j].ss) j++;
      |                ~^~~~~~~~~~
rect.cpp:124:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for (int i=0;i<vt.size();i++)
      |                  ~^~~~~~~~~~
rect.cpp:127:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         while (j<vt.size()&&vt[j].ff==vt[j-1].ff&&vt[j].ss-1==vt[j].ss) j++;
      |                ~^~~~~~~~~~
rect.cpp:129:12: warning: unused variable 'l' [-Wunused-variable]
  129 |         ll l=vt[i].ss;
      |            ^
rect.cpp:130:12: warning: unused variable 'r' [-Wunused-variable]
  130 |         ll r=vt[j].ss;
      |            ^
rect.cpp:131:14: warning: variable 'p' set but not used [-Wunused-but-set-variable]
  131 |         auto p=vt[j].ff;
      |              ^
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...