#include <iostream> #include "dzialka.h" #include "message.h" #include <deque> using namespace std; struct abc { long long x; int p; int k; long long r; long long m; }; struct ABC { int x; int y; }; abc tab[100000]; deque <ABC> Q; int main() { if (MyNodeId() > 0) return 0; int n=GetFieldWidth(); int m=GetFieldHeight(); long long wynik=0; // int n,m; // cin>>n>>m; for(int i=m-1; i>=0; i--) { for(int j=0; j<n; j++) { int k=IsUsableCell(i, j); // int k; // cin>>k; if(k==0)tab[j].x=0; else tab[j].x++; } for(int j=0; j<n; j++) { while(!Q.empty()&&tab[j].x<Q.back().x) { ABC a=Q.back(); tab[a.y-1].k=j+1; Q.pop_back(); // cout<<a.y<<endl; } tab[j].p=j+1; if(Q.empty()) { tab[j].m=j+1; } else { tab[j].m=j+1-Q.back().y; } ABC a; a.x=tab[j].x; a.y=j+1; Q.push_back(a); } while(!Q.empty()) { ABC a=Q.back(); tab[a.y-1].k=n+1; Q.pop_back(); // cout<<a.y<<endl; } for(int j=0; j<n; j++) { tab[j].r=tab[j].k-tab[j].p; } for(int j=0; j<n; j++) { wynik+=tab[j].x*tab[j].m*tab[j].r; } // for(int j=0;j<n;j++)cout<<" "<<i<<" "<<j<<" "<<tab[j].x<<" "<<tab[j].p<<" "<<tab[j].k<<" "<<tab[j].r<<" "<<tab[j].m<<endl; } cout << wynik << "\n"; // cin>>n; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #include <iostream> #include "dzialka.h" #include "message.h" #include <deque> using namespace std; struct abc { long long x; int p; int k; long long r; long long m; }; struct ABC { int x; int y; }; abc tab[100000]; deque <ABC> Q; int main() { if (MyNodeId() > 0) return 0; int n=GetFieldWidth(); int m=GetFieldHeight(); long long wynik=0; // int n,m; // cin>>n>>m; for(int i=m-1; i>=0; i--) { for(int j=0; j<n; j++) { int k=IsUsableCell(i, j); // int k; // cin>>k; if(k==0)tab[j].x=0; else tab[j].x++; } for(int j=0; j<n; j++) { while(!Q.empty()&&tab[j].x<Q.back().x) { ABC a=Q.back(); tab[a.y-1].k=j+1; Q.pop_back(); // cout<<a.y<<endl; } tab[j].p=j+1; if(Q.empty()) { tab[j].m=j+1; } else { tab[j].m=j+1-Q.back().y; } ABC a; a.x=tab[j].x; a.y=j+1; Q.push_back(a); } while(!Q.empty()) { ABC a=Q.back(); tab[a.y-1].k=n+1; Q.pop_back(); // cout<<a.y<<endl; } for(int j=0; j<n; j++) { tab[j].r=tab[j].k-tab[j].p; } for(int j=0; j<n; j++) { wynik+=tab[j].x*tab[j].m*tab[j].r; } // for(int j=0;j<n;j++)cout<<" "<<i<<" "<<j<<" "<<tab[j].x<<" "<<tab[j].p<<" "<<tab[j].k<<" "<<tab[j].r<<" "<<tab[j].m<<endl; } cout << wynik << "\n"; // cin>>n; } |