fork download
copy 
  1. /**
  2.  * a template matrix (2d array), with a sample application - solving the ioi mobile problem.
  3.  */
  4.  
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <vector>
  8. using namespace std;
  9.  
  10. typedef unsigned int uint;
  11.  
  12. template <class T> class matrix {
  13. protected:
  14.   uint myRows, myCols;
  15.   vector<T> myData;
  16. public:
  17.   matrix<T> () {}
  18.   matrix<T> (uint rows, uint cols): 
  19.     myRows(rows), myCols(cols),
  20.     myData(rows*cols) {} 
  21.  
  22.   void resize (int rows, int cols) {
  23.     myRows=rows; myCols=cols;
  24.     myData.resize(rows*cols);
  25.   }
  26.  
  27.   T& at(uint row, uint col) { return myData[row*myCols+col]; }
  28.   const T& at(uint row, uint col) const { return myData[row*myCols+col]; }
  29.  
  30.   void fill (T value) { ::fill(myData.begin(), myData.end(), value); }
  31.  
  32.   void print(ostream& out) const {
  33.     for (uint row=0; row<myRows; ++row) {
  34.       const T* temp = &myData[row*myCols];
  35.       for (uint col=0; col<myCols; ++col) {
  36.         out << temp[col] << " ";
  37.       }
  38.       out << endl;
  39.     }
  40.   }
  41.  
  42.   friend ostream& operator<< (ostream& out, const matrix<T>& m) { m.print(out); return out; }
  43. };
  44.  
  45.  
  46. class MobileNetworkKeepsValues: public matrix<short> {
  47.   // myData[r,c] holds the number of phones in row r, column c
  48.  
  49. public:
  50.   void add(uint X, uint Y, short A) {
  51.     at(X,Y) += A;
  52.   }
  53.  
  54.   uint sum(uint left, uint bottom, uint right, uint top) const {
  55.     uint result=0;
  56.     for (uint row=left; row<=right; ++row) {
  57.       const short* temp = &myData[row*myCols];
  58.       for (uint col=bottom; col<=top; ++col) {
  59.         result += temp[col];
  60.       }
  61.     }
  62.     return result;
  63.   } 
  64.  
  65. };
  66.  
  67.  
  68. class MobileNetworkKeepsSums: public matrix<int> {
  69.   // myData[r,c] holds the sum of phones in row r, columns [0..c]
  70.  
  71. public:
  72.   void add(uint X, uint Y, short A) {
  73.     int* temp = &myData[X*myCols];
  74.     for (uint col=Y; col<myCols; ++col) {
  75.       temp[col] += A;
  76.     }
  77.   }
  78.  
  79.   uint sum(uint left, uint bottom, uint right, uint top) const {
  80.     uint result=0;
  81.     for (uint row=left; row<=right; ++row) {
  82.       // sum from bottom to top = sum from 0 to top - sum from 0 to (bottom-1)
  83.       result += (at(row,top)-(bottom>0? at(row,bottom-1): 0));
  84.     }
  85.     return result;
  86.   } 
  87. };
  88.  
  89.  
  90. int main() {
  91.   MobileNetworkKeepsSums network;
  92.  
  93.   char commandCode;
  94.   uint S, //for command 0
  95.        X,Y, // for command 1
  96.        L,B,R,T; // for command 2
  97.   short A; // for command 1
  98.  
  99.   while (1) {
  100.     cin >> commandCode;
  101.     //cout << "command='" << commandCode << "'" << endl;
  102.     if (cin.eof()) break;
  103.     switch(commandCode) {
  104.       case '0':
  105.         cin >>  S;
  106.         network.resize(S,S);
  107.         network.fill(0);
  108.         break;
  109.       case '1':
  110.         cin >> X >> Y >> A;
  111.         network.add(X,Y,A);
  112.         //network.print(cout);
  113.         break;
  114.       case '2':
  115.         cin >> L >> B >> R >> T;
  116.         cout << network.sum(L,B,R,T) << endl;
  117.         break;
  118.       case '3':
  119.         return 0;
  120.       default:
  121.         cerr << "Unknown command " << commandCode << endl;
  122.     }
  123.   }
  124. }
  125.  
  126.  
  127.  
Success #stdin #stdout 0s 2864KB
comments (?)
stdin
copy 
0 4  		
1 1 2 3  		
2 0 0 2 2
1 1 1 2
1 1 2 -1
2 1 1 2 3
3
stdout
copy 
3
4
https://ideone.com/QGMRG
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!