Colour individual triangles in a sf::TriangleStrip

[BottleNeck]

Background:
I'm trying to make a falling sand simulation game which requires displaying a very large number of objects at once. I was drawing each "grain" of sand using a sf::RectangleShape, however for larger grids (e.g 500x500) this was far too many draw calls.

I'm currently trying to implement drawing of the sand using a sf::VertexArray. If I use sf::Triangle primitives, I'll have 6 vertices per grain, which is a lot for larger grid sizes.

Now I'm attempting to use the sf::TriangleStrip primitive to display the entire grid, using degenerate triangles to transition between rows. This reduces the number of vertices required by about two thirds, however now I have a problem with colouring the grains.

Question:
When using a sf::VertexArray to display a sf::TriangleStrip, is it possible to colour individual triangles within the strip different colours? Currently, if I want to colour two adjacent triangles in two different colours, the colours are interpolated between the vertices, forming a gradient. I want to be able to apply different colours to triangles without any gradient.

I've attached an image to show what I'm currently getting. I've drawn over the approximate locations of the triangles of the strip. I'd like the middle two triangles to be completely black.

[eXpl0it3r]

It's not possible with normal vertex coloring.

Not sure if there's some way with a shader, but that is usually the answer to anything you want to achieve graphics-wise.
In theory you could also use some texturing, mapping the triangle to a single color pixel. Not sure if that performs and won't cause some fun texture bleeding.